write first

Yesterday I summarized Quick Sort as a self-disciplined "author" (mistake). Yesterday, I said that writing a summary and merge sort article today is definitely not a pigeon (dog head).

Mergesort

Merge sort, as introduced yesterday quick sort It is also a sorting method based on the idea of ​​divide and conquer based on the merge operation. The so-called merge operation refers to the operation of merging two sorted sequences into one sequence. Therefore, based on the idea of ​​divide and conquer and the merge operation, the specific steps of merge sort are as follows.

Recursive method steps:

1. Divide the sequence to be sorted into two subsequences, and apply for two spaces of the size of two subsequences to store the two subsequences.
2. Two pointers L and R are allocated, and the initial positions respectively point to the starting positions of the two sorted sequences. Then allocate a pointer list, pointing to the starting position of the sequence to be sorted.
3. Compare the size of the elements pointed to by the two pointers, place the smaller element at the start of the sequence to be sorted, and add one to the corresponding pointer position (if L points to a small element, add one to L and list, otherwise add one to R and list).
4. Repeat step 3 until one of the two pointers of the subsequence reaches the end of the sequence.
5. Assign the remaining elements of the sequence to the end of the list directly from the current position of the list to the sequence to be sorted.

An illustration of the sorting steps is as follows:

Suppose the sequence to be sorted is [3,5,9,6,2,8,2,6][3,5,9,6,2,8,2,6][3,5,9,6,2, 8,2,6]

The process is as follows:

The complete code is as follows:
C language version:

#include <stdio.h>
#include <stdlib.h>

void merge(int nums[], int low, int mid, int high);
void mergeSort(int nums[], int low, int high);

int main(){
    int nums[8] = {3,5,9,6,2,8,2,6}; //sequence to be sorted
    mergeSort(nums, 0, 8-1);
    for(int i=0; i<8; i++) //output sorted sequence
        printf("%d ", nums[i]);
    printf("\n");
    return 0;
}

void merge(int nums[], int low, int mid, int high){
    int n_L, n_R, i, j, k;
    n_L = mid - low + 1; //length of subsequence 1
    n_R = high - mid; //length of subsequence 2
    int *nums_L = (int*)malloc(sizeof(int)*n_L);
    int *nums_R = (int*)malloc(sizeof(int)*n_R);
    for(i=0; i<n_L; i++) //Assign the first half of the sequence to be sorted to subsequence 1
        nums_L[i] = nums[low+i];
    for(j=0; j<n_R; j++) //Assign the second half of the sequence to be sorted to subsequence 2
        nums_R[j] = nums[mid+1+j];
    i = 0, j = 0, k = low;
    while(i < n_L && j < n_R) //Cyclic comparison of two pointers to two subsequences
        nums[k++] = nums_L[i] <= nums_R[j] ? nums_L[i++] : nums_R[j++];
    while(i < n_L) //Assign all remaining elements to the sequence to be sorted
        nums[k++] = nums_L[i++];
    while(j < n_R)
        nums[k++] = nums_R[j++];
    free(nums_L);
    free(nums_R);
}

void mergeSort(int nums[], int low, int high){
    int mid;
    if(low < high){
        mid = (low + high) / 2; //Evenly divide the sequence to be sorted
        mergeSort(nums, low, mid); //Sort first half
        mergeSort(nums, mid+1, high); //Sort the second half
        merge(nums, low, mid, high); //Merge two subsequences
    }
}

Python3 version:

class Solution:
    def merge(self, nums, low, mid, high):
        n_L = mid - low + 1 #length of subsequence 1
        n_R = high - mid #length of subsequence 2

        nums_L = [0] * n_L
        nums_R = [0] * n_R

        for i in range(n_L): #Assign the first half of the sequence to be sorted to subsequence 1
            nums_L[i] = nums[low+i]
        for j in range(n_R): #Assign the second half of the sequence to be sorted to subsequence 2
            nums_R[j] = nums[mid+1+j]

        i, j, k = 0, 0, low
        while i < n_L and j < n_R: #Two pointers to two subsequences cyclically compare the size
            if nums_L[i] < nums_R[j]:
                nums[k] = nums_L[i]
                i += 1
            else:
                nums[k] = nums_R[j]
                j += 1
            k += 1

        while i < n_L: #Assign all remaining elements to the column to be sorted
            nums[k] = nums_L[i]
            i += 1
            k += 1
        while j < n_R:
            nums[k] = nums_R[j]
            j += 1
            k += 1

    def mergeSort(self, nums, low, high):
        if low < high:
            mid = (high + low) // 2 #Equally divide the sequence to be sorted
            self.mergeSort(nums, low, mid) #Sort first half
            self.mergeSort(nums, mid+1, high) #Sort the second half
            self.merge(nums, low, mid, high) #Merge two subsequences

        return nums
        
nums = [1,4,7,2,5,1,4,3,8,6] #subsequence to be sorted

res = Solution().mergeSort(nums, 0, len(nums)-1)
print(res)

If there is any misunderstanding, please leave a message and exchange, if you need to reprint, please indicate the source.

If you don't understand, it must be because I didn't speak well. Please leave a message and I will continue to work hard.

Manually code the code and code the code. If it helps you, please leave a like, thank you.

above.