归并排序

归并排序使用分而治之的算法
Divide:将n个元素的序列分位两个n/2的子序列
Conquer:使用递归排序两个子序列
Combine:合并有序的子序列

import java.util.Arrays;

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

    }
    public static void mergeSort(int[] array, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            mergeSort(array, p, q);
            mergeSort(array, q + 1, r);
            merge(array, p, q, r);//合并
        }
    }

    /**
     * p <= q < r
     * array[p..q]和array[q+1..r]为有序序列
     * 将两个有序序列合并为array[p..r]
     */
    public static void merge(int[] array, int p, int q, int r) {
        int[] leftArray = Arrays.copyOfRange(array, p, q + 1);//array[p-q]
        int[] rightArray = Arrays.copyOfRange(array, q + 1, r + 1);//array[q+1,r]
        int llen = q - p + 1;
        int rlen = r - q;
        int i = 0;
        int j = 0;
        int k = p;
        for (; k < r + 1; k++) {
            if (i >= llen || j >= rlen) {
                break;
            }
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i++];
            } else {
                array[k] = rightArray[j++];
            }
        }
        while (i < llen ) {
            array[k++] = leftArray[i++];
        }
        while (j < rlen ) {
            array[k++] = rightArray[j++];
        }
    }
}

• 时间复杂度O(nlgn)
• 空间复杂度O(n)