Sorts the specified range of the array. @param vec vector of long values @param left the index of the first element, inclusive, to be sorted @param right the index of the last element, inclusive, to be sorted
(LongVec vec, int left, int right)
| 52 | * @param right the index of the last element, inclusive, to be sorted |
| 53 | */ |
| 54 | public static void sort(LongVec vec, int left, int right) { |
| 55 | // Use Quicksort on small arrays |
| 56 | if (right - left < QUICKSORT_THRESHOLD) { |
| 57 | sort(vec, left, right, true); |
| 58 | return; |
| 59 | } |
| 60 | |
| 61 | /* |
| 62 | * Index run[i] is the start of i-th run |
| 63 | * (ascending or descending sequence). |
| 64 | */ |
| 65 | int[] run = new int[MAX_RUN_COUNT + 1]; |
| 66 | int count = 0; |
| 67 | run[0] = left; |
| 68 | |
| 69 | // Check if the array is nearly sorted |
| 70 | for (int k = left; k < right; run[count] = k) { |
| 71 | if (vec.getQuick(k) < vec.getQuick(k + 1)) { // ascending |
| 72 | //noinspection StatementWithEmptyBody |
| 73 | while (++k <= right && vec.getQuick(k - 1) <= vec.getQuick(k)) ; |
| 74 | } else if (vec.getQuick(k) > vec.getQuick(k + 1)) { // descending |
| 75 | //noinspection StatementWithEmptyBody |
| 76 | while (++k <= right && vec.getQuick(k - 1) >= vec.getQuick(k)) ; |
| 77 | for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { |
| 78 | swap(vec, lo, hi); |
| 79 | } |
| 80 | } else { // equal |
| 81 | for (int m = MAX_RUN_LENGTH; ++k <= right && vec.getQuick(k - 1) == vec.getQuick(k); ) { |
| 82 | if (--m == 0) { |
| 83 | sort(vec, left, right, true); |
| 84 | return; |
| 85 | } |
| 86 | } |
| 87 | } |
| 88 | |
| 89 | /* |
| 90 | * The array is not highly structured, |
| 91 | * use Quicksort instead of merge sort. |
| 92 | */ |
| 93 | if (++count == MAX_RUN_COUNT) { |
| 94 | sort(vec, left, right, true); |
| 95 | return; |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | // Check special cases |
| 100 | if (run[count] == right++) { // The last run contains one element |
| 101 | run[++count] = right; |
| 102 | } else if (count == 1) { // The array is already sorted |
| 103 | return; |
| 104 | } |
| 105 | |
| 106 | /* |
| 107 | * Create temporary array, which is used for merging. |
| 108 | * Implementation note: variable "right" is increased by 1. |
| 109 | */ |
| 110 | |
| 111 | LongVec a; |