Performs a sort on the section of the array between the given indices using a mergesort with exponential search algorithm (in which the merge is performed by exponential search). n log(n) performance is guaranteed and in the average case it will be faster then any mergesort in which the merge is per
(Object[] in, Object[] out, int start,
int end)
| 2403 | * the end index + 1 |
| 2404 | */ |
| 2405 | @SuppressWarnings("unchecked") |
| 2406 | private static void mergeSort(Object[] in, Object[] out, int start, |
| 2407 | int end) { |
| 2408 | int len = end - start; |
| 2409 | // use insertion sort for small arrays |
| 2410 | if (len <= SIMPLE_LENGTH) { |
| 2411 | for (int i = start + 1; i < end; i++) { |
| 2412 | Comparable<Object> current = (Comparable<Object>) out[i]; |
| 2413 | Object prev = out[i - 1]; |
| 2414 | if (current.compareTo(prev) < 0) { |
| 2415 | int j = i; |
| 2416 | do { |
| 2417 | out[j--] = prev; |
| 2418 | } while (j > start |
| 2419 | && current.compareTo(prev = out[j - 1]) < 0); |
| 2420 | out[j] = current; |
| 2421 | } |
| 2422 | } |
| 2423 | return; |
| 2424 | } |
| 2425 | int med = (end + start) >>> 1; |
| 2426 | mergeSort(out, in, start, med); |
| 2427 | mergeSort(out, in, med, end); |
| 2428 | |
| 2429 | // merging |
| 2430 | |
| 2431 | // if arrays are already sorted - no merge |
| 2432 | if (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) { |
| 2433 | System.arraycopy(in, start, out, start, len); |
| 2434 | return; |
| 2435 | } |
| 2436 | int r = med, i = start; |
| 2437 | |
| 2438 | // use merging with exponential search |
| 2439 | do { |
| 2440 | Comparable<Object> fromVal = (Comparable<Object>) in[start]; |
| 2441 | Comparable<Object> rVal = (Comparable<Object>) in[r]; |
| 2442 | if (fromVal.compareTo(rVal) <= 0) { |
| 2443 | int l_1 = find(in, rVal, -1, start + 1, med - 1); |
| 2444 | int toCopy = l_1 - start + 1; |
| 2445 | System.arraycopy(in, start, out, i, toCopy); |
| 2446 | i += toCopy; |
| 2447 | out[i++] = rVal; |
| 2448 | r++; |
| 2449 | start = l_1 + 1; |
| 2450 | } else { |
| 2451 | int r_1 = find(in, fromVal, 0, r + 1, end - 1); |
| 2452 | int toCopy = r_1 - r + 1; |
| 2453 | System.arraycopy(in, r, out, i, toCopy); |
| 2454 | i += toCopy; |
| 2455 | out[i++] = fromVal; |
| 2456 | start++; |
| 2457 | r = r_1 + 1; |
| 2458 | } |
| 2459 | } while ((end - r) > 0 && (med - start) > 0); |
| 2460 | |
| 2461 | // copy rest of array |
| 2462 | if ((end - r) <= 0) { |