222 assert lo == hi; 223 ts.mergeForceCollapse(); 224 assert ts.stackSize == 1; 225 } 226 227 /** 228 * Sorts the specified portion of the specified array using a binary 229 * insertion sort. This is the best method for sorting small numbers 230 * of elements. It requires O(n log n) compares, but O(n^2) data 231 * movement (worst case). 232 * 233 * If the initial part of the specified range is already sorted, 234 * this method can take advantage of it: the method assumes that the 235 * elements from index {@code lo}, inclusive, to {@code start}, 236 * exclusive are already sorted. 237 * 238 * @param a the array in which a range is to be sorted 239 * @param lo the index of the first element in the range to be sorted 240 * @param hi the index after the last element in the range to be sorted 241 * @param start the index of the first element in the range that is 242 * not already known to be sorted (@code lo <= start <= hi} 243 * @param c comparator to used for the sort 244 */ 245 @SuppressWarnings("fallthrough") 246 private static <T> void binarySort(T[] a, int lo, int hi, int start, 247 Comparator<? super T> c) { 248 assert lo <= start && start <= hi; 249 if (start == lo) 250 start++; 251 for ( ; start < hi; start++) { 252 T pivot = a[start]; 253 254 // Set left (and right) to the index where a[start] (pivot) belongs 255 int left = lo; 256 int right = start; 257 assert left <= right; 258 /* 259 * Invariants: 260 * pivot >= all in [lo, left). 261 * pivot < all in [right, start). 262 */ 263 while (left < right) { 264 int mid = (left + right) >>> 1; 265 if (c.compare(pivot, a[mid]) < 0) 266 right = mid; 267 else 268 left = mid + 1; 269 } 270 assert left == right; 271 272 /* 273 * The invariants still hold: pivot >= all in [lo, left) and 274 * pivot < all in [left, start), so pivot belongs at left. Note 275 * that if there are elements equal to pivot, left points to the 276 * first slot after them -- that's why this sort is stable. 277 * Slide elements over to make room to make room for pivot. 278 */ 279 int n = start - left; // The number of elements to move 280 // Switch is just an optimization for arraycopy in default case 281 switch(n) { 282 case 2: a[left + 2] = a[left + 1]; 283 case 1: a[left + 1] = a[left]; 284 break; 285 default: System.arraycopy(a, left, a, left + 1, n); 286 } 287 a[left] = pivot; 288 } 289 } 290 291 /** 292 * Returns the length of the run beginning at the specified position in 293 * the specified array and reverses the run if it is descending (ensuring 294 * that the run will always be ascending when the method returns). 295 * 296 * A run is the longest ascending sequence with: 297 * 298 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 299 * 300 * or the longest descending sequence with: 301 * 302 * a[lo] > a[lo + 1] > a[lo + 2] > ... 303 * 304 * For its intended use in a stable mergesort, the strictness of the 305 * definition of "descending" is needed so that the call can safely 306 * reverse a descending sequence without violating stability. 307 * 308 * @param a the array in which a run is to be counted and possibly reversed 309 * @param lo index of the first element in the run 310 * @param hi index after the last element that may be contained in the run. 311 It is required that @code{lo < hi}. 312 * @param c the comparator to used for the sort 313 * @return the length of the run beginning at the specified position in 314 * the specified array 315 */ 316 private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 317 Comparator<? super T> c) { 318 assert lo < hi; 319 int runHi = lo + 1; 320 if (runHi == hi) 321 return 1; 322 323 // Find end of run, and reverse range if descending 324 if (c.compare(a[runHi++], a[lo]) < 0) { // Descending 325 while(runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) 326 runHi++; 327 reverseRange(a, lo, runHi); 328 } else { // Ascending 329 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) 330 runHi++; 331 } 332 333 return runHi - lo; 334 } 335 336 /** 337 * Reverse the specified range of the specified array. 338 * 339 * @param a the array in which a range is to be reversed 340 * @param lo the index of the first element in the range to be reversed 341 * @param hi the index after the last element in the range to be reversed 342 */ 343 private static void reverseRange(Object[] a, int lo, int hi) { 344 hi--; 345 while (lo < hi) { | 222 assert lo == hi; 223 ts.mergeForceCollapse(); 224 assert ts.stackSize == 1; 225 } 226 227 /** 228 * Sorts the specified portion of the specified array using a binary 229 * insertion sort. This is the best method for sorting small numbers 230 * of elements. It requires O(n log n) compares, but O(n^2) data 231 * movement (worst case). 232 * 233 * If the initial part of the specified range is already sorted, 234 * this method can take advantage of it: the method assumes that the 235 * elements from index {@code lo}, inclusive, to {@code start}, 236 * exclusive are already sorted. 237 * 238 * @param a the array in which a range is to be sorted 239 * @param lo the index of the first element in the range to be sorted 240 * @param hi the index after the last element in the range to be sorted 241 * @param start the index of the first element in the range that is 242 * not already known to be sorted ({@code lo <= start <= hi}) 243 * @param c comparator to used for the sort 244 */ 245 @SuppressWarnings("fallthrough") 246 private static <T> void binarySort(T[] a, int lo, int hi, int start, 247 Comparator<? super T> c) { 248 assert lo <= start && start <= hi; 249 if (start == lo) 250 start++; 251 for ( ; start < hi; start++) { 252 T pivot = a[start]; 253 254 // Set left (and right) to the index where a[start] (pivot) belongs 255 int left = lo; 256 int right = start; 257 assert left <= right; 258 /* 259 * Invariants: 260 * pivot >= all in [lo, left). 261 * pivot < all in [right, start). 262 */ 263 while (left < right) { 264 int mid = (left + right) >>> 1; 265 if (c.compare(pivot, a[mid]) < 0) 266 right = mid; 267 else 268 left = mid + 1; 269 } 270 assert left == right; 271 272 /* 273 * The invariants still hold: pivot >= all in [lo, left) and 274 * pivot < all in [left, start), so pivot belongs at left. Note 275 * that if there are elements equal to pivot, left points to the 276 * first slot after them -- that's why this sort is stable. 277 * Slide elements over to make room to make room for pivot. 278 */ 279 int n = start - left; // The number of elements to move 280 // Switch is just an optimization for arraycopy in default case 281 switch (n) { 282 case 2: a[left + 2] = a[left + 1]; 283 case 1: a[left + 1] = a[left]; 284 break; 285 default: System.arraycopy(a, left, a, left + 1, n); 286 } 287 a[left] = pivot; 288 } 289 } 290 291 /** 292 * Returns the length of the run beginning at the specified position in 293 * the specified array and reverses the run if it is descending (ensuring 294 * that the run will always be ascending when the method returns). 295 * 296 * A run is the longest ascending sequence with: 297 * 298 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 299 * 300 * or the longest descending sequence with: 301 * 302 * a[lo] > a[lo + 1] > a[lo + 2] > ... 303 * 304 * For its intended use in a stable mergesort, the strictness of the 305 * definition of "descending" is needed so that the call can safely 306 * reverse a descending sequence without violating stability. 307 * 308 * @param a the array in which a run is to be counted and possibly reversed 309 * @param lo index of the first element in the run 310 * @param hi index after the last element that may be contained in the run. 311 It is required that {@code lo < hi}. 312 * @param c the comparator to used for the sort 313 * @return the length of the run beginning at the specified position in 314 * the specified array 315 */ 316 private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi, 317 Comparator<? super T> c) { 318 assert lo < hi; 319 int runHi = lo + 1; 320 if (runHi == hi) 321 return 1; 322 323 // Find end of run, and reverse range if descending 324 if (c.compare(a[runHi++], a[lo]) < 0) { // Descending 325 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) 326 runHi++; 327 reverseRange(a, lo, runHi); 328 } else { // Ascending 329 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) 330 runHi++; 331 } 332 333 return runHi - lo; 334 } 335 336 /** 337 * Reverse the specified range of the specified array. 338 * 339 * @param a the array in which a range is to be reversed 340 * @param lo the index of the first element in the range to be reversed 341 * @param hi the index after the last element in the range to be reversed 342 */ 343 private static void reverseRange(Object[] a, int lo, int hi) { 344 hi--; 345 while (lo < hi) { |