TimSort：自适应的排序大师

import java.util.Arrays;

public class TimSortExample {
    private static final int MIN_MERGE = 32;
    
    public static void timSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        int minRun = minRunLength(MIN_MERGE);
        
        // 步骤1：将数组分解为多个run
        for (int i = 0; i < n; i += minRun) {
            int runEnd = Math.min(i + minRun - 1, n - 1);
            insertionSort(arr, i, runEnd);
        }
        
        // 步骤2：归并相邻的run
        int size = minRun;
        while (size < n) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = Math.min(left + size - 1, n - 1);
                int right = Math.min(left + 2 * size - 1, n - 1);
                
                if (mid < right) {
                    merge(arr, left, mid, right);
                }
            }
            size *= 2;
        }
    }
    
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int len1 = mid - left + 1;
        int len2 = right - mid;
        
        int[] leftArr = new int[len1];
        int[] rightArr = new int[len2];
        
        System.arraycopy(arr, left, leftArr, 0, len1);
        System.arraycopy(arr, mid + 1, rightArr, 0, len2);
        
        int i = 0, j = 0, k = left;
        
        while (i < len1 && j < len2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }
        
        while (i < len1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        
        while (j < len2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
    
    private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0;
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 12, 1, 6, 3, 7};
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        
        timSort(arr);
        
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }
}