This is a recursive mergesort that you might compare with the program you have:

It appears to work, but has not been thoroughly tested:

Code:

#include <stdio.h>
#include <stdlib.h>
#define MAX 200
void merge(int A[], int Index[], int l, int m, int r);
void mergesort(int *A, int *Index, int l, int r);
void printIt(int *A);
int main() {
int i;
int *A, *Index;
A = malloc(MAX * sizeof(int));
Index = malloc(MAX * sizeof(int));
if(!A || !Index) {
printf("memory allocation failed - terminating program");
return 1;
}
for(i = 0; i < MAX; i++) {
A[i] = rand() % 1000;
Index[i] = 0;
}
printf("\n\n Unsorted Data\n");
printIt(A);
getchar();
mergesort(A, Index, 0, MAX-1);
printf("\n\n Sorted Data\n");
printIt(A);
free(A);
free(Index);
printf("\n\n\t\t\t press enter when ready");
i = getchar();
return 0;
}
void mergesort(int *A, int *Index, int l, int r) {
int m;
if (l < r) {
m = (l + r) /2;
mergesort(A, Index, l, m);
mergesort(A, Index, m + 1, r);
merge(A, Index, l, m, r);
}
}
/* First, index m in the middle between lo and hi is determined. Then the
first part of the sequence (from lo to m) and the second part (from m+1
to hi) are sorted by recursive calls of mergesort. Then the two sorted halves
are merged by merge(). Recursion ends when lo = hi, i.e. when a sub-sequence
consists of only one element.
*/
void merge(int A[], int Index[], int l, int m, int r)
{
int i, j, k;
/* copy A to temp array Index */
for (i = l; i <= r; i++)
Index[i] = A[i];
i = l; j = m + 1; k = l;
/* copy back to A */
while (i <= m && j <= r)
if (Index[i] <= Index[j])
A[k++] = Index[i++];
else
A[k++] = Index[j++];
/* copy back remaining elements of first half (if any) */
while (i <= m)
A[k++] = Index[i++];
}
/*Merge() does most of the work in Mergesort. The two halves are first copied
into an extra array, Index. Then both halves are checked by the indicies i and
j, and the next number is copied back to array A, each time through the
while loop of merge();
*/
void printIt(int A[]) {
int i;
for(i = 0; i < MAX; i++)
printf(" %3d ", A[i]);
}

The output is good to see both the sorted, and unsorted int's, on the same page, if you keep the number of elements below 250 or so.