OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 import "dart:math" as math; | 5 import "dart:math" as math; |
6 | 6 |
7 import "utils.dart"; | 7 import "utils.dart"; |
8 | 8 |
9 /// Returns a position of the [value] in [sortedList], if it is there. | 9 /// Returns a position of the [value] in [sortedList], if it is there. |
10 /// | 10 /// |
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
167 // Special case the first split instead of directly calling | 167 // Special case the first split instead of directly calling |
168 // _mergeSort, because the _mergeSort requires its target to | 168 // _mergeSort, because the _mergeSort requires its target to |
169 // be different from its source, and it requires extra space | 169 // be different from its source, and it requires extra space |
170 // of the same size as the list to sort. | 170 // of the same size as the list to sort. |
171 // This split allows us to have only half as much extra space, | 171 // This split allows us to have only half as much extra space, |
172 // and it ends up in the original place. | 172 // and it ends up in the original place. |
173 int middle = start + ((end - start) >> 1); | 173 int middle = start + ((end - start) >> 1); |
174 int firstLength = middle - start; | 174 int firstLength = middle - start; |
175 int secondLength = end - middle; | 175 int secondLength = end - middle; |
176 // secondLength is always the same as firstLength, or one greater. | 176 // secondLength is always the same as firstLength, or one greater. |
177 var scratchSpace = new List<T>(secondLength); | 177 var scratchSpace = new List/*<T>*/(secondLength); |
178 _mergeSort(list, compare, middle, end, scratchSpace, 0); | 178 _mergeSort(list, compare, middle, end, scratchSpace, 0); |
179 int firstTarget = end - firstLength; | 179 int firstTarget = end - firstLength; |
180 _mergeSort(list, compare, start, middle, list, firstTarget); | 180 _mergeSort(list, compare, start, middle, list, firstTarget); |
181 _merge(compare, | 181 _merge(compare, |
182 list, firstTarget, end, | 182 list, firstTarget, end, |
183 scratchSpace, 0, secondLength, | 183 scratchSpace, 0, secondLength, |
184 list, start); | 184 list, start); |
185 } | 185 } |
186 | 186 |
187 /// Performs an insertion sort into a potentially different list than the | 187 /// Performs an insertion sort into a potentially different list than the |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
279 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), | 279 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), |
280 firstList, cursor1); | 280 firstList, cursor1); |
281 return; | 281 return; |
282 } | 282 } |
283 } | 283 } |
284 // First list empties first. Reached by break above. | 284 // First list empties first. Reached by break above. |
285 target[targetOffset++] = secondElement; | 285 target[targetOffset++] = secondElement; |
286 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), | 286 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2), |
287 secondList, cursor2); | 287 secondList, cursor2); |
288 } | 288 } |
OLD | NEW |