public class MergeSort {
    
    /**
     * 归并排序（自顶向下递归版本）
     */
    public static void sort(int[] arr) {
        if (arr.length <= 1) return;
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }
    
    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSort(arr, temp, left, mid);
        mergeSort(arr, temp, mid + 1, right);
        merge(arr, temp, left, mid, right);
    }
    
    /**
     * 合并两个已排序的子数组
     */
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // 将 arr[left..right] 复制到 temp[left..right]
        System.arraycopy(arr, left, temp, left, right - left + 1);
        
        int i = left;       // 左子数组指针
        int j = mid + 1;    // 右子数组指针
        int k = left;       // 合并后数组指针
        
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }
        
        // 复制剩余元素
        while (i <= mid) {
            arr[k++] = temp[i++];
        }
        while (j <= right) {
            arr[k++] = temp[j++];
        }
    }
    
    /**
     * 归并排序（自底向上迭代版本）
     * 避免递归开销，适合链表等数据结构
     */
    public static void sortIterative(int[] arr) {
        int n = arr.length;
        int[] temp = new int[n];
        
        for (int size = 1; size < n; size *= 2) {
            for (int left = 0; left < n - size; left += 2 * size) {
                int mid = left + size - 1;
                int right = Math.min(left + 2 * size - 1, n - 1);
                merge(arr, temp, left, mid, right);
            }
        }
    }
    
    /**
     * 归并排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        if (arr.length <= 1) return;
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) new Comparable[arr.length];
        mergeSortGeneric(arr, temp, 0, arr.length - 1);
    }
    
    private static <T extends Comparable<T>> void mergeSortGeneric(T[] arr, T[] temp, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        mergeSortGeneric(arr, temp, left, mid);
        mergeSortGeneric(arr, temp, mid + 1, right);
        mergeGeneric(arr, temp, left, mid, right);
    }
    
    private static <T extends Comparable<T>> void mergeGeneric(T[] arr, T[] temp, int left, int mid, int right) {
        System.arraycopy(arr, left, temp, left, right - left + 1);
        
        int i = left, j = mid + 1, k = left;
        
        while (i <= mid && j <= right) {
            if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }
        
        while (i <= mid) arr[k++] = temp[i++];
        while (j <= right) arr[k++] = temp[j++];
    }
    
    /**
     * 归并排序（原地优化版本）
     * 减少空间使用，但实现更复杂
     */
    public static void sortInPlace(int[] arr) {
        sortInPlace(arr, 0, arr.length - 1);
    }
    
    private static void sortInPlace(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        sortInPlace(arr, left, mid);
        sortInPlace(arr, mid + 1, right);
        mergeInPlace(arr, left, mid, right);
    }
    
    private static void mergeInPlace(int[] arr, int left, int mid, int right) {
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                i++;
            } else {
                int value = arr[j];
                // 将 arr[i..j-1] 向右移动一位
                System.arraycopy(arr, i, arr, i + 1, j - i);
                arr[i] = value;
                i++;
                mid++;
                j++;
            }
        }
    }
}