First and Ten Major Sorting Algorithms

2. Merging and sorting schematic diagram:

3. Recursive Implementation of Merging and Sorting Codes

Figure 1

Points for Attention
1. Why do Merge functions pass in these parameters?
Think about how to merge two arrays side by side without merging. Know the starting and ending points of the two arrays. You can calculate the starting and ending points of the two arrays by using the following three parameters (as shown in Figure 1 above).
The starting and ending points of the left part are Left and RightLeft-1, respectively.
The starting and ending points of the right part are RightLeft and RightEnd, respectively.

void Merge(int a[],int tmp[],int left,int rightLeft,int rightEnd){

    int leftEnd=rightLeft-1;
    int length=rightEnd-left+1;
    int i=left;

    while((left<=leftEnd)&&(rightLeft<=rightEnd)){
        if(a[left]<=a[rightLeft]){
            tmp[i++]=a[left++];
        } else{
            tmp[i++]=a[rightLeft++];
        }
    }
    while(left<=leftEnd){//Import all the tmp on the right, and leave the rest on the left.
        tmp[i++]=a[left++];
    }
    while(rightLeft<=rightEnd){
        tmp[i++]=a[rightLeft++];
    }
    //Return tmp back to a
    for(int i=0;i<length;i++,rightEnd--){
        a[rightEnd]=tmp[rightEnd];
    }

}

//The recursive method is well understood. The emphasis is on understanding the principle of recursive sorting first. It's better to memorize with graphs.
void MSort(int a[],int tmp[],int left,int right){
    if(left>=right){
        return;
    }
    int mid= (left+right)/2;
    MSort(a,tmp,left,mid);
    MSort(a,tmp,mid+1,right);
    Merge(a,tmp,left,mid+1,right);
    Dump(a,20,1);

}

2. Why does tmp, a temporary array, need to apply first and keep it with the parameters? Clearly, it's only used in merge functions.
Reason:
If you apply in the merge function, you will continue to apply for free space, inefficient.

If you apply outside, you only need to apply and release once.

void MergeSort(int a[],int size){
    if(size<=1) {
        printf("Too few elements");
        return;
    }
    int *tmp =(int*)malloc(size* sizeof(int));
    if(nullptr==tmp){
        printf("malloc memery error");
        return;
    }
    else{
        MSort(a,tmp,0,size-1);
        free(tmp);

    }
}

//test
void Dump(int a[],int size,int times){
    for(int i=0;i<size;++i){
        if(i==0){
            printf("sort %dth: ",times);
        }
        printf("%d ",a[i]);
    }
    printf("\r\n");
}

int main() {
    int a[20]={1,6,3,5,2,0,4,9,7,8,30,11,23,56,78,89,33,67,43,22};
    Dump(a,20,0);
    MergeSort(a,20);
    return 0;
}

The recursive implementation of merge sorting needs the limitation of the recursive algorithm itself, so the efficiency is not high. The merge algorithm can also be implemented in non-recursive form.

4. Non-recursive merging algorithm (to be added)