## 概要

``"Optimistic Sorting and Information Theoretic Complexity" Peter  McIlroy SODA (Fourth Annual ACM-SIAM Symposium on Discrete  Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993. ``

## 实现

• sort
`static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {     if (c == null) {         Arrays.sort(a, lo, hi);         return;     }      rangeCheck(a.length, lo, hi);     int nRemaining  = hi - lo;     if (nRemaining < 2)         return;  // Arrays of size 0 and 1 are always sorted      // If array is small, do a "mini-TimSort" with no merges     if (nRemaining < MIN_MERGE) {         int initRunLen = countRunAndMakeAscending(a, lo, hi, c);         binarySort(a, lo, hi, lo + initRunLen, c);         return;     }      /**      * March over the array once, left to right, finding natural runs,      * extending short natural runs to minRun elements, and merging runs      * to maintain stack invariant.      */     TimSort<T> ts = new TimSort<>(a, c);     int minRun = minRunLength(nRemaining);     do {         // Identify next run         int runLen = countRunAndMakeAscending(a, lo, hi, c);          // If run is short, extend to min(minRun, nRemaining)         if (runLen < minRun) {             int force = nRemaining <= minRun ? nRemaining : minRun;             binarySort(a, lo, lo + force, lo + runLen, c);             runLen = force;         }          // Push run onto pending-run stack, and maybe merge         ts.pushRun(lo, runLen);         ts.mergeCollapse();          // Advance to find next run         lo += runLen;         nRemaining -= runLen;     } while (nRemaining != 0);      // Merge all remaining runs to complete sort     assert lo == hi;     ts.mergeForceCollapse();     assert ts.stackSize == 1; } `

`if (c == null) {     Arrays.sort(a, lo, hi);     return; } `

`    if (nRemaining < 2)         return;  // Arrays of size 0 and 1 are always sorted      // If array is small, do a "mini-TimSort" with no merges     if (nRemaining < MIN_MERGE) {         int initRunLen = countRunAndMakeAscending(a, lo, hi, c);         binarySort(a, lo, hi, lo + initRunLen, c);         return;     }  `
1. 如果元素个数小于2,直接返回，因为这两个元素已经排序了
2. 如果元素个数小于一个阈值（默认为)，调用 `binarySort`，这是一个不包含合并操作的 `mini-TimSort`
3. 在关键的 `do-while` 循环中，不断地进行排序，合并，排序，合并，一直到所有数据都处理完。
`    TimSort<T> ts = new TimSort<>(a, c);     int minRun = minRunLength(nRemaining);     do {          ...      } while (nRemaining != 0); `
• minRunLength

`static int minRunLength(int n) {         assert n >= 0;         int r = 0;      // Becomes 1 if any 1 bits are shifted off         while (n >= MIN_MERGE) {             r |= (n & 1);             n >>= 1;         }         return n + r;     } `

``0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 55 28 56 28 57 29 58 29 59 30 60 30 61 31 62 31 63 32 64 16 65 17 66 17 67 17 68 17 69 18 70 18 71 18 72 18 73 19 74 19 75 19 76 19 77 20 78 20 79 20 80 20 81 21 82 21 83 21 84 21 85 22 86 22 87 22 88 22 89 23 90 23 91 23 92 23 93 24 94 24 95 24 96 24 97 25 98 25 99 25  ... ``

• do-while

`   TimSort<T> ts = new TimSort<>(a, c);     int minRun = minRunLength(nRemaining);     do {         // Identify next run         int runLen = countRunAndMakeAscending(a, lo, hi, c);          // If run is short, extend to min(minRun, nRemaining)         if (runLen < minRun) {             int force = nRemaining <= minRun ? nRemaining : minRun;             binarySort(a, lo, lo + force, lo + runLen, c);             runLen = force;         }          // Push run onto pending-run stack, and maybe merge         ts.pushRun(lo, runLen);         ts.mergeCollapse();          // Advance to find next run         lo += runLen;         nRemaining -= runLen;     } while (nRemaining != 0); `

`countRunAndMakeAscending` 会找到一个 `run` ，这个 `run` 必须是已经排序的，并且函数会保证它为升序，也就是说，如果找到的是一个降序的，会对其进行翻转。

• countRunAndMakeAscending
`private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,                                                 Comparator<? super T> c) {     assert lo < hi;     int runHi = lo + 1;     if (runHi == hi)         return 1;      // Find end of run, and reverse range if descending     if (c.compare(a[runHi++], a[lo]) < 0) { // Descending         while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)             runHi++;         reverseRange(a, lo, runHi);     } else {                              // Ascending         while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)             runHi++;     }      return runHi - lo; } `

`private static <T> void binarySort(T[] a, int lo, int hi, int start,                                    Comparator<? super T> c) {     assert lo <= start && start <= hi;     if (start == lo)         start++;     for ( ; start < hi; start++) {         T pivot = a[start];          // Set left (and right) to the index where a[start] (pivot) belongs         int left = lo;         int right = start;         assert left <= right;         /*          * Invariants:          *   pivot >= all in [lo, left).          *   pivot <  all in [right, start).          */         while (left < right) {             int mid = (left + right) >>> 1;             if (c.compare(pivot, a[mid]) < 0)                 right = mid;             else                 left = mid + 1;         }         assert left == right;          /*          * The invariants still hold: pivot >= all in [lo, left) and          * pivot < all in [left, start), so pivot belongs at left.  Note          * that if there are elements equal to pivot, left points to the          * first slot after them -- that's why this sort is stable.          * Slide elements over to make room for pivot.          */         int n = start - left;  // The number of elements to move         // Switch is just an optimization for arraycopy in default case         switch (n) {             case 2:  a[left + 2] = a[left + 1];             case 1:  a[left + 1] = a[left];                      break;             default: System.arraycopy(a, left, a, left + 1, n);         }         a[left] = pivot;     } } `

`  // If run is short, extend to min(minRun, nRemaining)     if (runLen < minRun) {         int force = nRemaining <= minRun ? nRemaining : minRun;         binarySort(a, lo, lo + force, lo + runLen, c);         runLen = force;     } `

`   // Push run onto pending-run stack, and maybe merge     ts.pushRun(lo, runLen);     ts.mergeCollapse();      // Advance to find next run     lo += runLen;     nRemaining -= runLen; `

• pushRun
`private void pushRun(int runBase, int runLen) {     this.runBase[stackSize] = runBase;     this.runLen[stackSize] = runLen;     stackSize++; } `

`/**  * Examines the stack of runs waiting to be merged and merges adjacent runs  * until the stack invariants are reestablished:  *  *     1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]  *     2. runLen[i - 2] > runLen[i - 1]  *  * This method is called each time a new run is pushed onto the stack,  * so the invariants are guaranteed to hold for i < stackSize upon  * entry to the method.  */ private void mergeCollapse() {     while (stackSize > 1) {         int n = stackSize - 2;         if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {             if (runLen[n - 1] < runLen[n + 1])                 n--;             mergeAt(n);         } else if (runLen[n] <= runLen[n + 1]) {             mergeAt(n);         } else {             break; // Invariant is established         }     } } `

• mergeAt

`mergeAt` 会把栈顶的两个 `run` 合并起来：

`   /**      * Merges the two runs at stack indices i and i+1.  Run i must be      * the penultimate or antepenultimate run on the stack.  In other words,      * i must be equal to stackSize-2 or stackSize-3.      *      * @param i stack index of the first of the two runs to merge  */ private void mergeAt(int i) {     assert stackSize >= 2;     assert i >= 0;     assert i == stackSize - 2 || i == stackSize - 3;      int base1 = runBase[i];     int len1 = runLen[i];     int base2 = runBase[i + 1];     int len2 = runLen[i + 1];     assert len1 > 0 && len2 > 0;     assert base1 + len1 == base2;      /*      * Record the length of the combined runs; if i is the 3rd-last      * run now, also slide over the last run (which isn't involved      * in this merge).  The current run (i+1) goes away in any case.      */     runLen[i] = len1 + len2;     if (i == stackSize - 3) {         runBase[i + 1] = runBase[i + 2];         runLen[i + 1] = runLen[i + 2];     }     stackSize--;      /*      * Find where the first element of run2 goes in run1. Prior elements      * in run1 can be ignored (because they're already in place).      */     int k = gallopRight(a[base2], a, base1, len1, 0, c);     assert k >= 0;     base1 += k;     len1 -= k;     if (len1 == 0)         return;      /*      * Find where the last element of run1 goes in run2. Subsequent elements      * in run2 can be ignored (because they're already in place).      */     len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);     assert len2 >= 0;     if (len2 == 0)         return;      // Merge remaining runs, using tmp array with min(len1, len2) elements     if (len1 <= len2)         mergeLo(base1, len1, base2, len2);     else         mergeHi(base1, len1, base2, len2); } `

`gallop` 和 `merge` 就不展开了。

1