Merge sort (top-down)

Merge sort

Merge sort adopts divide and conquer + outer sort (does not occupy additional memory space), top-down

The merging and sorting can be roughly divided into the following steps:

First, you must "divide". Suppose there is an array of [8, 4, 5, 7, 1, 3, 6, 2], and the result of division is to divide by 2 through recursion every time: [8,4,5,7,1,3,6,2]- > [[8,4,5,7] and [1,3,6,2]] -->[8,4], [5,7], [1,3], [6,2]. The only difference is that sorting and merging are required in the process of re division.

At this time, 8 and 4 are sorted. With the help of a new array, 4 and 8 are filled in order; Then put back the original array to get: [4,8,5,7,1,3,6,2]

After row 5 and 7 [4,8,5,7,1,3,6,2]

After sorting 4,8,5,7 [4,5,7,8,1,3,6,2], the idea of merging is reflected here; It is also the use of backtracking

Sort by analogy 1, 3 and 6, 2 and 1, 3, 2, 6

Finally, perform the overall ranking again: [4,5,7,8,1,2,3,6]. All sorts are compared in half. If the half is 8, both sides are already in order; Then compare the two sides alternately.

Specific codes are as follows:

/*
nums:Represents the array to be sorted
left:Starting index of the array after splitting
right:Right boundary of array
temp:Indicates the space required for the outer row
*/
public static void mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right)/ 2;
            mergeSort(nums, left, mid, temp);//Recursion every time mid All elements on the left
            mergeSort(nums, mid + 1, right, temp);//every time mid Elements on the right
            merge(nums, left, mid, right, temp);//sort
        }
    }

    public static void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int l = left;
        int r = mid + 1;
        int i = 0;
//Here is the sorting process
        while (l <= mid && r <= right) {
            if (nums[l] <= nums[r]) {
                temp[i] = nums[l];
                i++;
                l++;
            } else {
                temp[i] = nums[r];
                i++;
                r++;
            }
        }
  //Here is how to process the remaining elements, such as 3,5,6,7,8;After sorting above, you can directly assign 678 to temp
        while (l <= mid) {
            temp[i] = nums[l];
            i++;
            l++;
        }
        while (r <= right) {
            temp[i] = nums[r];
            i++;
            r++;
        }
   //The following is the temp Array arranged elements are transferred to the original array
        int leftTemp = left;
        i = 0;
        while (leftTemp <= right) {
            nums[leftTemp] = temp[i];
            i++;
            leftTemp++;
        }
    }

Description:

Merge sort is similar to a complete binary tree, and according to the proof given in the fourth edition of algorithm: merge sort is an asymptotically optimal algorithm based on comparison sort; Because the time complexity of merge sort is O(NlgN) in both the best and worst cases, the upper and lower limits of comparison sort are nlgn. However, the specific situation should be a different matter. For small arrays, it may be faster to select or insert sorting. These sorting algorithms are also based on comparison; That is to say, apart from comparison, there are better sorting algorithms without comparison, and the spatial complexity O(n) of merge sorting is not optimal.

All the essays are just for simple review and reference. You still need to read books or study systematically. Blogs are just a little bit of personal cognition.

Tags: data structure

Posted by ssidellq on Tue, 31 May 2022 05:17:19 +0530