| 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 |