Personal blog portal

Algorithm diagram

In a typical divide-and-conquer method, divide is to decompose the sorting problem into the smallest unit (i.e., 1 number sorting) and synthesize the sorting result of the subtree into the sorting result of the parent of the next level. The following figure describes the sorting process

1. I’m going to recurse to the sequencepointsSolve to the smallest unit
2. Step by step calculationcureThe results of the

implementation

private static void doSort(int[] arr, int[] tmp, int start, int end) {
        if (start < end) {
            int mid = (end + start) / 2;
            doSort(arr, tmp, start, mid);
            doSort(arr, tmp, mid + 1, end); merge(arr, tmp, start, mid, end); }}private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                tmp[t++] = arr[i++];
            }

            if(arr[i] > arr[j]) { tmp[t++] = arr[j++]; }}while (i <= mid) {
            tmp[t++] = arr[i++];
        }

        while (j <= end) {
            tmp[t++] = arr[j++];
        }

        System.arraycopy(tmp, 0, arr, start, end - start + 1);
    }
Copy the code

Time complexity

The O(nlogn) array is divided into a binary tree. The height of the binary tree is log2n, and the number of times each layer needs to be compared is n f(n) = n * log2n = O(nlogn).

Spatial complexity

O(n) uses a temp array to cache data that is processed in the middle, so you need to consider space waste when there is a large amount of data

The complete code

class MergeSort {

    private static void sort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int[] tmp = new int[array.length];
        int length = array.length;
        doSort(array, tmp, 0, length - 1);
    }

    private static void doSort(int[] arr, int[] tmp, int start, int end) {
        if (start < end) {
            int mid = (end + start) / 2;
            doSort(arr, tmp, start, mid);
            doSort(arr, tmp, mid + 1, end); merge(arr, tmp, start, mid, end); }}private static void merge(int[] arr, int[] tmp, int start, int mid, int end){
        int i = start;
        int j = mid + 1;
        int t = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                tmp[t++] = arr[i++];
            }

            if(arr[i] > arr[j]) { tmp[t++] = arr[j++]; }}while (i <= mid) {
            tmp[t++] = arr[i++];
        }

        while (j <= end) {
            tmp[t++] = arr[j++];
        }

        System.arraycopy(tmp, 0, arr, start, end - start + 1);
    }

    public static void main(String[] args) {
        int[] array = {111.52.77.98.36.12.12.48};
        sort(array);
        System.out.println(arrayToString(array));
    }

    private static String arrayToString(int[] array) {
        StringBuilder builder = new StringBuilder();
        for (int t : array) {
            builder.append(t + "");
        }
        returnbuilder.toString(); }}Copy the code

reference

www.cnblogs.com/chengxiao/p…