# Detailed explanation - Mergesort - C language Python recursive implementation

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)
```