排序--归并排序

概念

采用归并思想/分治法：把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

时间复杂度

• 平均：O(nlog(n))
• 最好：O(nlog(n))
• 最坏：O(nlog(n))

空间复杂度

O(1)

稳定性

稳定

代码

public class MergeSort implements Sort {

    @Override
    public int[] sort(int[] arr) {
        return sort(arr, 0, arr.length - 1);
    }

    private int[] sort(int[] arr, int l, int h) {
        // 递归终止条件，返回单个元素数组
        if (l == h) {
            return new int[]{arr[l]};
        }

        // 二等分，分别递归排序
        int mid = l + (h - l) / 2;
        int[] leftArr = sort(arr, l, mid);
        int[] rightArr = sort(arr, mid + 1, h);

        int[] newArr = new int[leftArr.length + rightArr.length];

        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newArr[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }

        while (i < leftArr.length) {
            newArr[m++] = leftArr[i++];
        }

        while (j < rightArr.length) {
            newArr[m++] = rightArr[j++];
        }

        return newArr;
    }
}