Deeply explore the optimization of TimSort on merge sort algorithm and the realization of Java

Introduction to the
The average complexity of MergeSort is n*O(log n), the best case is O(n), and the worst case is n*O(log n). And TimSort is a stability sort. The idea is to partition the rows first and then merge the partitions. It looks like step 1 of MergeSort, but there is some optimization for reverse and large-scale data.

The optimization idea of merge sort
Merge sort has the following optimization methods:

Like quicksort 1, you can use insertion sort or selection sort for small arrays to avoid recursive calls.
Before the call to merge(), you can determine whether a[mid] is less than or equal to a[mid+1] under 1. If so, then instead of merging, the array is already in order. The reason is simple: since the two subarrays are already in order, a[mid] is the maximum value of the first subarray, and a[mid+1] is the minimum value of the second subarray. When a [mid] < When =a[mid+1], the array is ordered as a whole.
To save time copying elements into the helper array, swap the roles of the original array and the helper array at each level of the recursive call.
The merge process in the merge() method needs to determine whether i and j have crossed the line, that is, one side has been exhausted. Another way to do this is to get rid of code that detects if one half of the code has been used up. The next step is to copy the second half of the array a[] in descending order to aux[] and merge it from both ends. For arrays {1,2,3} and {2,3,5}, the first subarray is copied as usual, the second is copied from behind, and the final element in aux[] is {1,2,3,5,3,2}. The disadvantage of this method is that it makes merge sort unstable. The code is implemented as follows:

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
for (int k = lo; k <= mid; k++) {
  aux[k] = a[k];
}
for (int k = mid + 1;k <= hi; k++) {
  aux[k] = a[hi - k + mid + 1];
}
int i = lo, j = hi;   // From the ends to the middle 
for (int k = lo; k <= hi; k++)
  if (aux[i] <= aux[j]) a[k] = aux[i++];
  else a[k] = aux[j--];
}

TimSort steps

partition

The idea of partitioning is to scan the group of 1 times, and take the continuous positive sequence (if it is sorted in ascending order, then the positive sequence is an ascending sequence), or [strict] (to ensure the stability of the sorting algorithm) anti-sequence as a partition (run). If it is anti-sequence, reverse the elements in the partition by 1. For example,
1,2,3,6,4,5,8,6,4 partition results are
[1,2,3,6],[4,5,8],[6,4]
Then reverse the antisequence
[1,2,3,6],[4,5,8],[4,6]

merge

So if you take an extreme case where you have a partition length of 10,000, 10, 1,000, 10, 10, 10, 10, 10, 10, 10, we want to have 10 tens merged into 20, 20 and 1000 merged into 1020 and so on, and if you're merging from left to right, you're using 10,000 every time and you're merging into smaller arrays, it's too expensive. So we can use a strategy to optimize the order of merges.

The instance

For example, ComparableTimSort.sort () in java USES one run stack to determine whether it should be merged,

    if (nRemaining < MIN_MERGE) {
      int initRunLen = countRunAndMakeAscending(a, lo, hi);
      binarySort(a, lo, hi, lo + initRunLen);
      return;
    }

The sorting is less than MIN_MERGE (32). After partitioning, the sorting is directly inserted with 2 points

int minRun = minRunLength(nRemaining);
    do {
      // Find out the 1 At the same time, the reverse sequence is reversed 
      int runLen = countRunAndMakeAscending(a, lo, hi);

      // ensure run stack In the run Is greater than minRun  If the current partition is too small, fetch the element complement from the back 
      if (runLen < minRun) {
        int force = nRemaining <= minRun ? nRemaining : minRun;
        binarySort(a, lo, lo + force, lo + runLen);
        runLen = force;
      }

      // the run In the  run stack In the 
      ts.pushRun(lo, runLen);
      // To decide whether or not to merge, i It starts at the top of the stack until you can't merge 
      //1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] 
      //2. runLen[i - 2] > runLen[i - 1]
      ts.mergeCollapse();


      lo += runLen;
      nRemaining -= runLen;
    } while (nRemaining != 0);

    // Merge all remaining runs to complete sort
    assert lo == hi;
    // Merge the rest run
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;

I'm looking at one of the more important functions in there

/**
*  If after 2 a run The sum of the lengths over the front 1 Length, then use the middle position run And shorter in front and back run1 A merger 
*  If after 2 a run The sum of the lengths over the front 1 One is short, then put the back 2 a run merge 
*/
 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
      }
    }
  }