Diagram

Explain

	Algorithms are recursive. Here is a simple non recursive implementation.
	That is, 2, 2 merge and sort, and then 4, 4 merge and sort until it is finished. Do not group recursively.
	Note that some code implementations on the Internet write merge conditions as left < right, not left < = right or right < left. The resu lt of writing left < right is that stable sorting becomes unstable.

Code

#include <stdio.h>
#include <math.h> 
#define  N 11
int mergeSort(int n,int * arr,int *temp)
{	//Merge sort in non recursive way 	
//Step 1: cycle the grouping length, starting from the 0 power of 2 and multiplying by 2 each time, i.e. 1,2,4,8,16... Not less than n 	
	for  (int groupLen=1;groupLen<n;groupLen=groupLen<<1)	
	{		
		int resCount=0;//The subscript of the temp array. The location where each merging result is stored in temp 		
		int groupCount=ceil(n*1.0/groupLen); //Number of groups, if less than one group, one group 		
		int mergeCount=groupCount>>1;//The number of merging was once in two groups. Single group does not merge. 			
		//The second step is to merge the two groups.		
		for (int i = 0;i<mergeCount;i++)		
		{		
			int left = (i*groupLen)<<1; //Start position of left group 			
			int leftSide=left+groupLen; //The end of the left group.			
			int right=leftSide;  //Start position of right group 			
			int rightSide=(n<right+groupLen)?n:right+groupLen; 	//The end of the right group.						
			//Merge two arrays. Merging can encapsulate an inline function without affecting performance. This is the benefit of non recursion. Recursion cannot inline. 			
			while (left<leftSide&&right<rightSide) 			
			{	//Merge: put the smaller one of the two group headers into a temporary array.					
			if(arr[left]<=arr[right]) //If you use arr [left] < arr [right], it is unstable.						
				temp[resCount++]=arr[left++];						
			else		temp[resCount++]=arr[right++];				
			}    		
			while (left<leftSide) //The rest of the left group is copied to the temporary array 					
				temp[resCount++]=arr[left++];			
			while (right<rightSide) //Copy the rest of the right group to the temporary array 				
				temp[resCount++]=arr[right++];		    
			for (left = i<<1; left < rightSide;left++) //Copy the merging result data of the temporary array back to the original array. 		        
				arr[left] = temp[left];    	
		}
	}
}
//Test it.
int main(){	
	int n = N;
	int arr[N]={6,3,6,8,6,4,7,8,9,2,1};
	int temp[N];	
	mergeSort(n,arr,temp);	
	for(int i = 0;i < n;i++)		
		printf("%d,",arr[i]) ;	printf("\b \n");
}

end...