Merge Sort issue when removing the array copy step
- by Ime Prezime
I've been having an issue that I couldn't debug for quite some time. I am trying to implement a MergeSort algorithm with no additional steps of array copying by following Robert Sedgewick's algorithm in "Algorithm's in C++" book.
Short description of the algorithm:
The recursive program is set up to sort b, leaving results in a. Thus, the recursive calls are written to leave their result in b, and we use the basic merge program to merge those files from b into a. In this way, all the data movement is done during the course of the merges.
The problem is that I cannot find any logical errors but the sorting isn't done properly. Data gets overwritten somewhere and I cannot determine what logical error causes this. The data is sorted when the program is finished but it is not the same data any more.
For example, Input array: { A, Z, W, B, G, C } produces the array: { A, G, W, W, Z, Z }.
I can obviously see that it must be a logical error somewhere, but I have been trying to debug this for a pretty long time and I think a fresh set of eyes could maybe see what I'm missing cause I really can't find anything wrong.
My code:
static const int M = 5;
void insertion(char** a, int l, int r)
{
int i,j;
char * temp;
for (i = 1; i < r + 1; i++)
{
temp = a[i];
j = i;
while (j > 0 && strcmp(a[j-1], temp) > 0)
{
a[j] = a[j-1];
j = j - 1;
}
a[j] = temp;
}
}
//merging a and b into c
void merge(char ** c,char ** a, int N, char ** b, int M)
{
for (int i = 0, j = 0, k = 0; k < N+M; k++)
{
if (i == N)
{
c[k] = b[j++];
continue;
}
if (j == M)
{
c[k] = a[i++];
continue;
}
c[k] = strcmp(a[i], b[j]) < 0 ? a[i++] : b[j++];
}
}
void mergesortAux(char ** a, char ** b, int l, int r)
{
if(r - l <= M)
{
insertion(a, l, r);
return;
}
int m = (l + r)/2;
mergesortAux(b, a, l, m); //merge sort left
mergesortAux(b, a, m+1, r); //merge sort right
merge(a+l, b+l, m-l+1, b+m+1, r-m); //merge
}
void mergesort(char ** a,int l, int r, int size)
{
static char ** aux = (char**)malloc(size * sizeof(char*));
for(int i = l; i < size; i++)
aux[i] = a[i];
mergesortAux(a, aux, l, r);
free(aux);
}
