190 assert lo == hi; 191 ts.mergeForceCollapse(); 192 assert ts.stackSize == 1; 193 } 194 195 /** 196 * Sorts the specified portion of the specified array using a binary 197 * insertion sort. This is the best method for sorting small numbers 198 * of elements. It requires O(n log n) compares, but O(n^2) data 199 * movement (worst case). 200 * 201 * If the initial part of the specified range is already sorted, 202 * this method can take advantage of it: the method assumes that the 203 * elements from index {@code lo}, inclusive, to {@code start}, 204 * exclusive are already sorted. 205 * 206 * @param a the array in which a range is to be sorted 207 * @param lo the index of the first element in the range to be sorted 208 * @param hi the index after the last element in the range to be sorted 209 * @param start the index of the first element in the range that is 210 * not already known to be sorted (@code lo <= start <= hi} 211 */ 212 @SuppressWarnings("fallthrough") 213 private static void binarySort(Object[] a, int lo, int hi, int start) { 214 assert lo <= start && start <= hi; 215 if (start == lo) 216 start++; 217 for ( ; start < hi; start++) { 218 @SuppressWarnings("unchecked") 219 Comparable<Object> pivot = (Comparable) a[start]; 220 221 // Set left (and right) to the index where a[start] (pivot) belongs 222 int left = lo; 223 int right = start; 224 assert left <= right; 225 /* 226 * Invariants: 227 * pivot >= all in [lo, left). 228 * pivot < all in [right, start). 229 */ 230 while (left < right) { 231 int mid = (left + right) >>> 1; 232 if (pivot.compareTo(a[mid]) < 0) 233 right = mid; 234 else 235 left = mid + 1; 236 } 237 assert left == right; 238 239 /* 240 * The invariants still hold: pivot >= all in [lo, left) and 241 * pivot < all in [left, start), so pivot belongs at left. Note 242 * that if there are elements equal to pivot, left points to the 243 * first slot after them -- that's why this sort is stable. 244 * Slide elements over to make room to make room for pivot. 245 */ 246 int n = start - left; // The number of elements to move 247 // Switch is just an optimization for arraycopy in default case 248 switch(n) { 249 case 2: a[left + 2] = a[left + 1]; 250 case 1: a[left + 1] = a[left]; 251 break; 252 default: System.arraycopy(a, left, a, left + 1, n); 253 } 254 a[left] = pivot; 255 } 256 } 257 258 /** 259 * Returns the length of the run beginning at the specified position in 260 * the specified array and reverses the run if it is descending (ensuring 261 * that the run will always be ascending when the method returns). 262 * 263 * A run is the longest ascending sequence with: 264 * 265 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 266 * 267 * or the longest descending sequence with: 268 * 269 * a[lo] > a[lo + 1] > a[lo + 2] > ... 270 * 271 * For its intended use in a stable mergesort, the strictness of the 272 * definition of "descending" is needed so that the call can safely 273 * reverse a descending sequence without violating stability. 274 * 275 * @param a the array in which a run is to be counted and possibly reversed 276 * @param lo index of the first element in the run 277 * @param hi index after the last element that may be contained in the run. 278 It is required that @code{lo < hi}. 279 * @return the length of the run beginning at the specified position in 280 * the specified array 281 */ 282 @SuppressWarnings("unchecked") 283 private static int countRunAndMakeAscending(Object[] a, int lo, int hi) { 284 assert lo < hi; 285 int runHi = lo + 1; 286 if (runHi == hi) 287 return 1; 288 289 // Find end of run, and reverse range if descending 290 if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending 291 while(runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0) 292 runHi++; 293 reverseRange(a, lo, runHi); 294 } else { // Ascending 295 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0) 296 runHi++; 297 } 298 299 return runHi - lo; 300 } 301 302 /** 303 * Reverse the specified range of the specified array. 304 * 305 * @param a the array in which a range is to be reversed 306 * @param lo the index of the first element in the range to be reversed 307 * @param hi the index after the last element in the range to be reversed 308 */ 309 private static void reverseRange(Object[] a, int lo, int hi) { 310 hi--; 311 while (lo < hi) { | 190 assert lo == hi; 191 ts.mergeForceCollapse(); 192 assert ts.stackSize == 1; 193 } 194 195 /** 196 * Sorts the specified portion of the specified array using a binary 197 * insertion sort. This is the best method for sorting small numbers 198 * of elements. It requires O(n log n) compares, but O(n^2) data 199 * movement (worst case). 200 * 201 * If the initial part of the specified range is already sorted, 202 * this method can take advantage of it: the method assumes that the 203 * elements from index {@code lo}, inclusive, to {@code start}, 204 * exclusive are already sorted. 205 * 206 * @param a the array in which a range is to be sorted 207 * @param lo the index of the first element in the range to be sorted 208 * @param hi the index after the last element in the range to be sorted 209 * @param start the index of the first element in the range that is 210 * not already known to be sorted ({@code lo <= start <= hi}) 211 */ 212 @SuppressWarnings("fallthrough") 213 private static void binarySort(Object[] a, int lo, int hi, int start) { 214 assert lo <= start && start <= hi; 215 if (start == lo) 216 start++; 217 for ( ; start < hi; start++) { 218 @SuppressWarnings("unchecked") 219 Comparable<Object> pivot = (Comparable) a[start]; 220 221 // Set left (and right) to the index where a[start] (pivot) belongs 222 int left = lo; 223 int right = start; 224 assert left <= right; 225 /* 226 * Invariants: 227 * pivot >= all in [lo, left). 228 * pivot < all in [right, start). 229 */ 230 while (left < right) { 231 int mid = (left + right) >>> 1; 232 if (pivot.compareTo(a[mid]) < 0) 233 right = mid; 234 else 235 left = mid + 1; 236 } 237 assert left == right; 238 239 /* 240 * The invariants still hold: pivot >= all in [lo, left) and 241 * pivot < all in [left, start), so pivot belongs at left. Note 242 * that if there are elements equal to pivot, left points to the 243 * first slot after them -- that's why this sort is stable. 244 * Slide elements over to make room to make room for pivot. 245 */ 246 int n = start - left; // The number of elements to move 247 // Switch is just an optimization for arraycopy in default case 248 switch (n) { 249 case 2: a[left + 2] = a[left + 1]; 250 case 1: a[left + 1] = a[left]; 251 break; 252 default: System.arraycopy(a, left, a, left + 1, n); 253 } 254 a[left] = pivot; 255 } 256 } 257 258 /** 259 * Returns the length of the run beginning at the specified position in 260 * the specified array and reverses the run if it is descending (ensuring 261 * that the run will always be ascending when the method returns). 262 * 263 * A run is the longest ascending sequence with: 264 * 265 * a[lo] <= a[lo + 1] <= a[lo + 2] <= ... 266 * 267 * or the longest descending sequence with: 268 * 269 * a[lo] > a[lo + 1] > a[lo + 2] > ... 270 * 271 * For its intended use in a stable mergesort, the strictness of the 272 * definition of "descending" is needed so that the call can safely 273 * reverse a descending sequence without violating stability. 274 * 275 * @param a the array in which a run is to be counted and possibly reversed 276 * @param lo index of the first element in the run 277 * @param hi index after the last element that may be contained in the run. 278 It is required that {@code lo < hi}. 279 * @return the length of the run beginning at the specified position in 280 * the specified array 281 */ 282 @SuppressWarnings("unchecked") 283 private static int countRunAndMakeAscending(Object[] a, int lo, int hi) { 284 assert lo < hi; 285 int runHi = lo + 1; 286 if (runHi == hi) 287 return 1; 288 289 // Find end of run, and reverse range if descending 290 if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending 291 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0) 292 runHi++; 293 reverseRange(a, lo, runHi); 294 } else { // Ascending 295 while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0) 296 runHi++; 297 } 298 299 return runHi - lo; 300 } 301 302 /** 303 * Reverse the specified range of the specified array. 304 * 305 * @param a the array in which a range is to be reversed 306 * @param lo the index of the first element in the range to be reversed 307 * @param hi the index after the last element in the range to be reversed 308 */ 309 private static void reverseRange(Object[] a, int lo, int hi) { 310 hi--; 311 while (lo < hi) { |