Merge sort

Merge and sort related contents .

Merge sort is a typical application of divide and conquer , And it is a stable sort method , But you need to use extra space .

The idea of merging and sorting ：

1. Divide the array into subsequences , Cut length only 2 perhaps 1 The subsequence .
2. Then use the temporary array , Sort subsequences , Merge , Then copy the values of the temporary array back to the original array .
3. Repeat the operation 1~2 step , Until sorting is complete .

The advantage of merge sorting is that the time complexity of the best case and the worst case is O(nlogn), So it is a relatively stable sorting method .

https://lixj.fun/upload/2021/07/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F-2697907b116b410c923b1b70a71bc1f6.gif

Algorithm complexity ：O(nlogn)

Algorithm space complexity ：O(n)

Algorithm stability ： Stable

public class MergeSortNew {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // int[]  Array name  = new int[ The length of the array ];
        int[] temp = new int[arr.length];
        //  Merger 
        sort(arr, 0, arr.length - 1, temp);
    }

    public static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //  Merge the elements on the left 
            sort(arr, left, mid, temp);
            //  Merge right elements 
            sort(arr, mid + 1, right, temp);
            //  Merge subsequences 
            merge(arr, left, mid, right, temp);
        }
    }


    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        // i Is the starting point of the first group , j Is the starting point of the second group 
        int i = left, j = mid + 1;
        // m For the end of the first group , n For the end of the second group 
        int m = mid, n = right;
        // k Used to point to temp Where is the array currently placed 
        int k = 0;
        //  Compare two ordered sequences circularly ,  Fill in array temp
        while (i <= m && j <= n) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //  If the comparison is over ,  There are still a few left in the first group ,  Then fill in all temp
        while (i <= m) {
            temp[k++] = arr[i++];
        }
        //  If the comparison is over ,  There are still a few left in the second group ,  Then fill in all temp
        while (j <= n) {
            temp[k++] = arr[j++];
        }

        //  Fill in the ordered numbers back to array The corresponding position of the array 
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }

    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Copy

Copyright: use Creative Commons signature 4.0 International license agreement to license Links:https://lixj.fun/archives/ Merge sort