Java實現世界上最快的排序演演算法Timsort的範例程式碼

// List sort()    
default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
              //陣列排序
        Arrays.sort(a, (Comparator) c);
              ...
    }

// Arrays.sort
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {
              // 廢棄版本
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }

public static int[] sort(int[] arr) throws Exception {
        // 開始遍歷第一個元素後的所有元素
        for (int i = 1; i < arr.length; i++) {
            // 需要插入的元素
            int tmp = arr[i];
            // 從已排序最後一個元素開始，如果當前元素比插入元素大，就往後移動
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 將元素插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }

    public static int[] binarySort(int[] arr) throws Exception {
        for (int i = 1; i < arr.length; i++) {
            // 需要插入的元素
            int tmp = arr[i];
            // 通過二分查詢直接找到插入位置
            int j = Math.abs(Arrays.binarySearch(arr, 0, i, tmp) + 1);
            // 找到插入位置後，通過陣列複製向後移動，騰出元素位置
            System.arraycopy(arr, j, arr, j + 1, i - j);
            // 將元素插入
            arr[j] = tmp;
        }
        return arr;
    }

public static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
        // 跳出遞迴
        if (start >= end) {
            return;
        }
        // 待分割的陣列長度
        int len = end - start;
        int mid = (len >> 1) + start;
        int left = start; // 左子陣列開始索引
        int right = mid + 1; // 右子陣列開始索引
        // 遞迴切割左子陣列，直到只有一個元素
        mergeSortRecursive(arr, result, left, mid);
        // 遞迴切割右子陣列，直到只有一個元素
        mergeSortRecursive(arr, result, right, end);
        int k = start;
        while (left <= mid && right <= end) {
            result[k++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
        }
        while (left <= mid) {
            result[k++] = arr[left++];
        }
        while (right <= end) {
            result[k++] = arr[right++];
        }
        for (k = start; k <= end; k++) {
            arr[k] = result[k];
        }
    }

    public static int[] merge_sort(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        mergeSortRecursive(arr, result, 0, len - 1);
        return arr;
    }

private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0;      // 如果低位任何一位是1，就會變成1
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

private void mergeCollapse() {
      
       // 當存在兩個以上run執行合併檢查
        while (stackSize > 1) {

          // 表示 Y
            int n = stackSize - 2; 
           
          // Z <= Y + X 
            if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { 

              // 如果 Z < X 合併Z+Y ，否則合併X+Y
              if (runLen[n - 1] < runLen[n + 1])
                    n--;
                
                // 合併相鄰的兩個run，也就是runLen[n] 和 runLen[n+1]
                mergeAt(n); 
            } else if (runLen[n] <= runLen[n + 1]) {
                
                // Y <= X 合併 Y+X
                mergeAt(n);
            } else {
                
                // 滿足兩個條件，跳出迴圈
                break; 
            }
        }
    }