Recursive and non recursive implementation of merge sort code

Merge sort
Merge sort is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. It is important to note that merge sort is a stable sort method. By combining the ordered subsequences, a completely ordered sequence is obtained. That is, make each subsequence ordered first, and then make the subsequence ordered between segments. If two ordered tables are merged into one ordered table, it is called 2-way merge.

Algorithm description
Merge operation works as follows:
Step 1: apply for a space whose size is the sum of two sorted sequences, which is used to store the merged sequences
Step 2: set two Pointers to the starting positions of the two sorted sequences
Step 3: compare the elements to which the two Pointers point, select a relatively small element to put into the merge space, and move the pointer to the next location

Time complexity:
The time complexity is O(nlogn), which is the best, worst, and average time performance of the algorithm.
The space complexity is O(n).
The number of comparison operations is between nlogn over 2 and nlogn minus n plus 1.
The number of assignments is 2nlogn. The space complexity of merge algorithm is: 0 (n)
Merge sort is a relatively memory-intensive but efficient and stable algorithm.
(excerpt from baidu baike)

Code implementation
Top up implementation:
// merge using auxiliary arrays

void MergeSort(int *aux, int *data, int l, int m, int h)
{
 int k=0, i=l, j=m+1;

 for(k=l; k<=h; k++)
 {
  if(i>m)     aux[k]=data[j++];
  else if(j>h)    aux[k]=data[i++];
  else if(data[i]<data[j])        aux[k]=data[i++];
  else    aux[k]=data[j++];
 }
 for(k=l; k<=h; k++)
  data[k]=aux[k];
}

Recursive sort (top down merge)

void Sort(int *aux, int *data, int l, int h)
{
 if(l<h)
 {
  int m=l+(h-l)/2;
  Sort(aux, data, l, m);
  Sort(aux, data, m+1, h);
  MergeSort(aux,data, l, m, h);
 }
}

The process of sorting with non-recursion (bottom-up merge)

void NonRerMerSort(int *aux, int *data, int l, int h)
{
 int i=l, j;
 for(i=l; i<=h; i=2*i)
 {
  for(j=l; j<=h-i; j+=2*i)
   MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
 }
}