归并排序

import java.util.Arrays;

/**
 * @author leekari
 * @date 2020/10/14 15:42
 * @description
 */

/**
 * 归并排序
 */
public class MergeSort {
    public static int[] mergeSort(int l, int r, int[] arr){
        if (l == r) {
            return new int[]{arr[l]};
        }
        int mid = l + (r - l) / 2;
        int[] leftArr = mergeSort(l, mid, arr);
        int[] rightArr = mergeSort(mid + 1, r, arr);
        int[] newArr = new int[leftArr.length + rightArr.length];

        int i = 0, j = 0, k = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newArr[k++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length){
            newArr[k++] = leftArr[i++];
        }
        while (j < rightArr.length){
            newArr[k++] = rightArr[j++];
        }
        System.err.println(Arrays.toString(newArr));
        return newArr;
    }

    public static void main(String[] args) {
        int[] i = {3,2,5,1,6,8,9};
        System.err.println(Arrays.toString(mergeSort(0, i.length - 1, i)));
    }
}