# 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...

Keywords: less REST

Added by digitallookout on Mon, 28 Oct 2019 16:10:50 +0200