| OLD | NEW |
| 1 part of dart._internal; | 1 part of dart._internal; |
| 2 class Sort {static const int _INSERTION_SORT_THRESHOLD = 32; | 2 class Sort {static const int _INSERTION_SORT_THRESHOLD = 32; |
| 3 static void sort(List a, int compare(a, b)) { | 3 static void sort(List a, int compare(a, b)) { |
| 4 _doSort(a, 0, a.length - 1, compare); | 4 _doSort(a, 0, a.length - 1, compare); |
| 5 } | 5 } |
| 6 static void sortRange(List a, int from, int to, int compare(a, b)) { | 6 static void sortRange(List a, int from, int to, int compare(a, b)) { |
| 7 if ((from < 0) || (to > a.length) || (to < from)) { | 7 if ((from < 0) || (to > a.length) || (to < from)) { |
| 8 throw "OutOfRange"; | 8 throw "OutOfRange"; |
| 9 } | 9 } |
| 10 _doSort(a, from, to - 1, compare); | 10 _doSort(a, from, to - 1, compare); |
| 11 } | 11 } |
| 12 static void _doSort(List a, int left, int right, int compare(a, b)) { | 12 static void _doSort(List a, int left, int right, int compare(a, b)) { |
| 13 if ((right - left) <= _INSERTION_SORT_THRESHOLD) { | 13 if ((right - left) <= _INSERTION_SORT_THRESHOLD) { |
| 14 _insertionSort(a, left, right, compare); | 14 _insertionSort(a, left, right, compare); |
| 15 } | 15 } |
| 16 else { | 16 else { |
| 17 _dualPivotQuicksort(a, left, right, compare); | 17 _dualPivotQuicksort(a, left, right, compare); |
| 18 } | 18 } |
| 19 } | 19 } |
| 20 static void _insertionSort(List a, int left, int right, int compare(a, b)) { | 20 static void _insertionSort(List a, int left, int right, int compare(a, b)) { |
| 21 for (int i = left + 1; | 21 for (int i = left + 1; i <= right; i++) { |
| 22 i <= right; | |
| 23 i++) { | |
| 24 var el = a[i]; | 22 var el = a[i]; |
| 25 int j = i; | 23 int j = i; |
| 26 while ((j > left) && (compare(a[j - 1], el) > 0)) { | 24 while ((j > left) && (compare(a[j - 1], el) > 0)) { |
| 27 a[j] = a[j - 1]; | 25 a[j] = a[j - 1]; |
| 28 j--; | 26 j--; |
| 29 } | 27 } |
| 30 a[j] = el; | 28 a[j] = el; |
| 31 } | 29 } |
| 32 } | 30 } |
| 33 static void _dualPivotQuicksort(List a, int left, int right, int compare(a, b))
{ | 31 static void _dualPivotQuicksort(List a, int left, int right, int compare(a, b))
{ |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 92 a[index1] = el1; | 90 a[index1] = el1; |
| 93 a[index3] = el3; | 91 a[index3] = el3; |
| 94 a[index5] = el5; | 92 a[index5] = el5; |
| 95 a[index2] = a[left]; | 93 a[index2] = a[left]; |
| 96 a[index4] = a[right]; | 94 a[index4] = a[right]; |
| 97 int less = left + 1; | 95 int less = left + 1; |
| 98 int great = right - 1; | 96 int great = right - 1; |
| 99 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); | 97 bool pivots_are_equal = (compare(pivot1, pivot2) == 0); |
| 100 if (pivots_are_equal) { | 98 if (pivots_are_equal) { |
| 101 var pivot = pivot1; | 99 var pivot = pivot1; |
| 102 for (int k = less; | 100 for (int k = less; k <= great; k++) { |
| 103 k <= great; | |
| 104 k++) { | |
| 105 var ak = a[k]; | 101 var ak = a[k]; |
| 106 int comp = compare(ak, pivot); | 102 int comp = compare(ak, pivot); |
| 107 if (comp == 0) continue; | 103 if (comp == 0) continue; |
| 108 if (comp < 0) { | 104 if (comp < 0) { |
| 109 if (k != less) { | 105 if (k != less) { |
| 110 a[k] = a[less]; | 106 a[k] = a[less]; |
| 111 a[less] = ak; | 107 a[less] = ak; |
| 112 } | 108 } |
| 113 less++; | 109 less++; |
| 114 } | 110 } |
| (...skipping 13 matching lines...) Expand all Loading... |
| 128 else { | 124 else { |
| 129 a[k] = a[great]; | 125 a[k] = a[great]; |
| 130 a[great--] = ak; | 126 a[great--] = ak; |
| 131 break; | 127 break; |
| 132 } | 128 } |
| 133 } | 129 } |
| 134 } | 130 } |
| 135 } | 131 } |
| 136 } | 132 } |
| 137 else { | 133 else { |
| 138 for (int k = less; | 134 for (int k = less; k <= great; k++) { |
| 139 k <= great; | |
| 140 k++) { | |
| 141 var ak = a[k]; | 135 var ak = a[k]; |
| 142 int comp_pivot1 = compare(ak, pivot1); | 136 int comp_pivot1 = compare(ak, pivot1); |
| 143 if (comp_pivot1 < 0) { | 137 if (comp_pivot1 < 0) { |
| 144 if (k != less) { | 138 if (k != less) { |
| 145 a[k] = a[less]; | 139 a[k] = a[less]; |
| 146 a[less] = ak; | 140 a[less] = ak; |
| 147 } | 141 } |
| 148 less++; | 142 less++; |
| 149 } | 143 } |
| 150 else { | 144 else { |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 183 _doSort(a, great + 2, right, compare); | 177 _doSort(a, great + 2, right, compare); |
| 184 if (pivots_are_equal) { | 178 if (pivots_are_equal) { |
| 185 return;} | 179 return;} |
| 186 if (less < index1 && great > index5) { | 180 if (less < index1 && great > index5) { |
| 187 while (compare(a[less], pivot1) == 0) { | 181 while (compare(a[less], pivot1) == 0) { |
| 188 less++; | 182 less++; |
| 189 } | 183 } |
| 190 while (compare(a[great], pivot2) == 0) { | 184 while (compare(a[great], pivot2) == 0) { |
| 191 great--; | 185 great--; |
| 192 } | 186 } |
| 193 for (int k = less; | 187 for (int k = less; k <= great; k++) { |
| 194 k <= great; | |
| 195 k++) { | |
| 196 var ak = a[k]; | 188 var ak = a[k]; |
| 197 int comp_pivot1 = compare(ak, pivot1); | 189 int comp_pivot1 = compare(ak, pivot1); |
| 198 if (comp_pivot1 == 0) { | 190 if (comp_pivot1 == 0) { |
| 199 if (k != less) { | 191 if (k != less) { |
| 200 a[k] = a[less]; | 192 a[k] = a[less]; |
| 201 a[less] = ak; | 193 a[less] = ak; |
| 202 } | 194 } |
| 203 less++; | 195 less++; |
| 204 } | 196 } |
| 205 else { | 197 else { |
| (...skipping 23 matching lines...) Expand all Loading... |
| 229 } | 221 } |
| 230 } | 222 } |
| 231 } | 223 } |
| 232 _doSort(a, less, great, compare); | 224 _doSort(a, less, great, compare); |
| 233 } | 225 } |
| 234 else { | 226 else { |
| 235 _doSort(a, less, great, compare); | 227 _doSort(a, less, great, compare); |
| 236 } | 228 } |
| 237 } | 229 } |
| 238 } | 230 } |
| OLD | NEW |