1. Principle and implementation of the simple version of TimSort sorting algorithm

TimSort sorting algorithm is the default sorting algorithm for object arrays in Python and Java. The essence of the TimSort sorting algorithm is a merge sort algorithm, but a lot of optimizations have been made on the merge sort algorithm. The data we need to sort in daily life is usually not completely random, but partially ordered or partially reversed, so TimSort makes full use of the ordered parts for merge sorting. Now we provide a simple version of the TimSort sorting algorithm, which mainly makes the following optimizations:

1.1 Utilize the originally ordered fragments

First define a minimum merge length. Check the originally ordered fragments in the array. If the ordered length is less than the specified minimum merge length, then expand the ordered fragments through insertion sort (the reason for this is to avoid merging fragments with smaller lengths, because this The efficiency is relatively low). Push the starting index position and ordered length of the ordered fragment onto the stack.

1.2 Avoid merging a longer ordered fragment with a smaller ordered fragment, because this is less efficient:

(1) If there are at least three ordered sequences in the stack, we use X , Y, Z respectively represent the three existing sequence fragments from the top of the stack downward, and are merged when the lengths of the three satisfy X+Y>=Z.

(1.1) If 1.2) Otherwise, pop X and Y off the stack, and push the merged result onto the stack. Note that in fact we will not actually pop the stack. There are some techniques in writing code that can achieve the same effect and be more efficient.

(2) If the condition of X+Y>=Z is not met or there are only two sequences in the stack, we use X and Y to represent the lengths of the two existing sequences from the top of the stack downwards. If Y performs the merge, and then pushes the merged ordered fragment results onto the stack.

1.3 When merging two ordered fragments, the so-called gallop mode is used, which can reduce the length of data involved in the merge

Assume that the two ordered fragments that need to be merged are X and Y respectively. , if the first m elements of the X segment are smaller than the first element of the Y segment, then these m elements do not actually need to participate in the merge, because the m elements are still at their original positions after the merge. In the same way, if the last n elements of the Y fragment are larger than the last element of X, then the last n elements of Y do not need to participate in the merge. This reduces the length of the merged array (the simple version does not do this), and also reduces the length of data copied back and forth between the array to be sorted and the auxiliary array, thereby improving the efficiency of the merge.

2. Java source code

package datastruct;
 
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
 
public class SimpleTimSort<T extends Comparable<? super T>>{
    //最小歸并長度
    private static final int MIN_MERGE = 16;
    //待排序數(shù)組
    private final T[] a;
    //輔助數(shù)組
    private T[] aux;
    //用兩個數(shù)組表示棧
    private int[] runsBase = new int[40];
    private int[] runsLen = new int[40];
    //表示棧頂指針
    private int stackTop = 0;
     
    @SuppressWarnings("unchecked")
    public SimpleTimSort(T[] a){
        this.a = a;
        aux = (T[]) Array.newInstance(a[0].getClass(), a.length);
    }
     
    //T[from, to]已有序，T[to]以后的n元素插入到有序的序列中
    private void insertSort(T[] a, int from, int to, int n){
        int i = to + 1;
        while(n > 0){
            T tmp = a[i];
            int j;
            for(j = i-1; j >= from && tmp.compareTo(a[j]) < 0; j--){
                a[j+1] = a[j];
            }
            a[++j] = tmp;
            i++;
            n--;
        }
    }
     
    //返回從a[from]開始，的最長有序片段的個數(shù)
    private int maxAscendingLen(T[] a, int from){
        int n = 1;
        int i = from;
         
        if(i >= a.length){//超出范圍
            return 0;
        }
         
        if(i == a.length-1){//只有一個元素
            return 1;
        }
         
        //至少兩個元素
        if(a[i].compareTo(a[i+1]) < 0){//升序片段
            while(i+1 <= a.length-1 && a[i].compareTo(a[i+1]) <= 0){
                i++;
                n++;
            }
            return n;
        }else{//降序片段，這里是嚴格的降序，不能有>=的情況，否則不能保證穩(wěn)定性
            while(i+1 <= a.length-1 && a[i].compareTo(a[i+1]) > 0){
                i++;
                n++;
            }
            //對降序片段逆序
            int j = from;
            while(j < i){
                T tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                j++;
                i--;
            }
            return n;
        }
    }
     
    //對有序片段的起始索引位置和長度入棧
    private void pushRun(int base, int len){
        runsBase[stackTop] = base;
        runsLen[stackTop] = len;
        stackTop++;
    }
     
    //返回-1表示不需要歸并棧中的有序片段
    public int needMerge(){
        if(stackTop > 1){//至少兩個run序列
            int x = stackTop - 2;
            //x > 0 表示至少三個run序列
            if(x > 0 && runsLen[x-1] <= runsLen[x] + runsLen[x+1]){
                if(runsLen[x-1] < runsLen[x+1]){
                    //說明 runsLen[x+1]是runsLen[x]和runsLen[x-1]中最大的值
                    //應(yīng)該先合并runsLen[x]和runsLen[x-1]這兩段run
                    return --x;
                }else{
                    return x;
                }
            }else
            if(runsLen[x] <= runsLen[x+1]){
                return x;
            }else{
                return -1;
            }
        }
        return -1;
    }
     
    //返回后一個片段的首元素在前一個片段應(yīng)該位于的位置
    private int gallopLeft(T[] a, int base, int len, T key){
        int i = base;
        while(i <= base + len - 1){
            if(key.compareTo(a[i]) >= 0){
                i++;
            }else{
                break;
            }
        }
        return i;
    }
     
    //返回前一個片段的末元素在后一個片段應(yīng)該位于的位置
    private int gallopRight(T[] a, int base, int len, T key){
        int i = base + len -1;
        while(i >= base){
            if(key.compareTo(a[i]) <= 0){
                i--;
            }else{
                break;
            }
        }
        return i;
    }
     
    public void mergeAt(int x){
        int base1 = runsBase[x];
        int len1 = runsLen[x];
         
        int base2 = runsBase[x+1];
        int len2 = runsLen[x+1];
         
        //合并run[x]和run[x+1],合并后base不用變,長度需要發(fā)生變化
        runsLen[x] = len1 + len2; 
        if(stackTop == x + 3){
            //棧頂元素下移，省去了合并后的先出棧，再入棧
            runsBase[x+1] = runsBase[x+2];
            runsLen[x+1] = runsLen[x+2];
        }
        stackTop--;
         
        //飛奔模式，減小歸并的長度
        int from = gallopLeft(a, base1, len1, a[base2]);
        if(from == base1+len1){
            return;
        }
        int to = gallopRight(a, base2, len2, a[base1+len1-1]);
         
        //對兩個需要歸并的片段長度進行歸并
        System.arraycopy(a, from, aux, from, to - from + 1);
        int i = from;
        int iend = base1 + len1 - 1;
         
        int j = base2;
        int jend = to;
         
        int k = from;
        int kend = to;
         
        while(k <= kend){
            if(i > iend){
                a[k] = aux[j++];
            }else
            if(j > jend){
                a[k] = aux[i++];
            }else
            if(aux[i].compareTo(aux[j]) <= 0){//等號保證排序的穩(wěn)定性
                a[k] = aux[i++];
            }else{
                a[k] = aux[j++];
            }
            k++;
        }
    }
     
    //強制歸并已入棧的序列
    private void forceMerge(){
        while(stackTop > 1){
            mergeAt(stackTop-2);
        }
    }
     
    //timSort的主方法
    public void timSort(){
        //n表示剩余長度
        int n = a.length; 
         
        if(n < 2){
            return;
        }
         
        //待排序的長度小于MIN_MERGE,直接采用插入排序完成
        if(n < MIN_MERGE){
            insertSort(a, 0, 0, a.length-1);
            return;
        }
         
        int base = 0;
        while(n > 0){
            int len = maxAscendingLen(a, base);
            if(len < MIN_MERGE){
                int abscent = n > MIN_MERGE ?  MIN_MERGE - len : n - len;
                insertSort(a, base, base + len-1, abscent);
                len = len + abscent;
            }
            pushRun(base, len);
            n = n - len;
            base = base + len;
             
            int x;
            while((x  = needMerge()) >= 0 ){
                mergeAt(x);
            }
        }
        forceMerge();
    }
     
    public static void main(String[] args){
         
        //隨機產(chǎn)生測試用例
        Random rnd = new Random(System.currentTimeMillis());
        boolean flag = true;
        while(flag){
             
            //首先產(chǎn)生一個全部有序的數(shù)組
            Integer[] arr1 = new Integer[1000];
            for(int i = 0; i < arr1.length; i++){
                arr1[i] = i;
            }
             
            //有序的基礎(chǔ)上隨機交換一些值
            for(int i = 0; i < (int)(0.1*arr1.length); i++){
                int x,y,tmp;
                x = rnd.nextInt(arr1.length);
                y = rnd.nextInt(arr1.length);
                tmp = arr1[x];
                arr1[x] = arr1[y];
                arr1[y] = tmp;
            }
             
            //逆序部分數(shù)據(jù)
            for(int i = 0; i <(int)(0.05*arr1.length); i++){
                int x = rnd.nextInt(arr1.length);
                int y = rnd.nextInt((int)(arr1.length*0.01)+x);
                if(y >= arr1.length){
                    continue;
                }
                while(x < y){
                    int tmp;
                    tmp = arr1[x];
                    arr1[x] = arr1[y];
                    arr1[y] = tmp;
                    x++;
                    y--;
                }
            }
             
            Integer[] arr2 = arr1.clone();
            Integer[] arr3 = arr1.clone();
            Arrays.sort(arr2);
             
            SimpleTimSort<Integer> sts = new SimpleTimSort<Integer>(arr1);
            sts.timSort();
             
            //比較SimpleTimSort排序和庫函數(shù)提供的排序結(jié)果比較是否一致
            //如果沒有打印任何結(jié)果，說明排序結(jié)果正確
            if(!Arrays.deepEquals(arr1, arr2)){
                for(int i = 0; i < arr1.length; i++){
                    if(!arr1[i].equals(arr2[i])){
                        System.out.printf("%d: arr1 %d  arr2 %d\n",i,arr1[i],arr2[i]);
                    }
                }
                System.out.println(Arrays.deepToString(arr3));
                flag = false;
            }
        }
    }
}

3. Issues that should be paid attention to with the TimSort algorithm

The TimSort algorithm will only merge two consecutive fragments, so as to ensure the stability of the algorithm.

There is a certain relationship between the minimum merge length and the length of the stack. If the minimum merge length is increased, the length of the stack should also be increased, otherwise it may cause the risk of the stack going out of bounds (the stack in the code is implemented by an array of length 40 of).

4. The full version of the TimSort algorithm

In fact, the full version of the TimSort algorithm will have a lot of optimizations on the above-mentioned simple TimSort algorithm. For example, when the ordered sequence is smaller than the minimum merge length, we can use a method similar to binary search to find the position where it should be inserted to extend the length of the array. Another example is that in the galloping mode, binary search is used to find the position of the first element of the second sequence in the first sequence. At the same time, a smaller auxiliary space can be used to complete the merge. Interested students can view the source code in Java Come and learn.