C language implements eight sorts of sort merge sort

What is merging order ？

Merge sort It is an effective sorting algorithm based on merge operation , The algorithm adopts Divide and conquer method A very typical application .

Merges ordered subsequences , You get a perfectly ordered sequence ; So let's make each subsequence in order , Then make the subsequence segments in order . If two ordered tables are merged into one ordered table , It's called a two-way merge .

The steps are shown in the figure ：

  So how can we achieve it ？

1. Recursive method

The code is as follows ：

//  Merge sort 
// Merge two ordered arrays 
void Sort(int*a,int left,int mid,int right){
	int*p=(int*)malloc(sizeof(int)*(right-left+1)); // Opening up a size is right-left+1 Space  
	int p1=left;
	int p2=mid+1;
	int p3=0;
	while(p1<=mid&&p2<=right){
		if(a[p1]<a[p2]){
			p[p3++]=a[p1++];
		}
		else{
			p[p3++]=a[p2++];
		}
	}
	while(p1<=mid)
		p[p3++]=a[p1++];
	while(p2<=right)
		p[p3++]=a[p2++];
	for(int j=0;j<p3;j++){
		a[left+j]=p[j];
	}
	free(p); 
}
void MergeSort(int*a,int left,int right){
	int mid;
	if(left>=right){ // When an array has only one element , Can be seen as orderly  
		return;
	}
	mid=(left+right)/2;
	MergeSort(a,left,mid); // Sort left half array  
	MergeSort(a,mid+1,right); // Sort the right half of the array  
	Sort(a,left,mid,right); // Merge two ordered arrays  
} 

  In this way, we have completed the recursive version of merge sorting

2. Non recursive version

As we can see from the picture , Finally, the first to merge is the array with only one element , Then we can use non recursion to realize the last step first ：

// Non recursive writing  
void MergeSort2(int*a,int n){
	int*tmp = (int*)malloc(sizeof(int)*n);
	int gap=1;// Similar to the last step of recursion directly first 
	while(gap<n){
		for(int i = 0 ; i < n; i += 2*gap){
			int start1=i,end1=i+gap-1; // The first interval  
			int start2=gap+i,end2=2*gap+i-1; // The second interval 
			int index=i;// Each initialization position is the starting position of the first interval  
			while(start1<=end1&&start2<=end2){
				if(a[start1]<a[start2])
					tmp[index++]=a[start1++];
				else
					tmp[index++]=a[start2++];
			}
			while(start1<=end1)
				tmp[index++]=a[start1++];	
			while(start2<=end2)
				tmp[index++]=a[start2++];  
		}
		memcpy(a,tmp,n*sizeof(int));
		gap *= 2;
	} 
	free(tmp);
} 

  We will start with the size of the array by 1 Start , Merge in pairs , Finally complete the recursive operation , Is that the end ？

Let's look at each merged array ：

What we have here is just 9 An array of element sizes , Why did you cross the border so many times .

 

 

  Then how should we modify it , Make it impossible to cross the border ？

Here we need to readjust our range ：

int start1=i,end1=i+gap-1; // The first interval  
int start2=gap+i,end2=2*gap+i-1; // The second interval

  This is the interval we defined before , From the above figure, we can also see that in addition to start1 He's a good boy and doesn't cross the line , The others have crossed the line , Then we should criticize and correct them .

Here we need to consider three situations ：

1. If end1 Transboundary

2. If end2 Transboundary

3. If start2 Transboundary

The modification operation is as follows ：

            if(end1>=n){
		      end1=n-1;
			} 
			if(start2>=n){
				start2=n;
				end2=n-1;
			}
			if(start2<n&&end2>=n){
				end2=n-1;
			}

  In this way, we can well realize our operation