mergesort for array of pointers to structs

Question

I'm trying to write a generic mergesort for arrays holding pointers to different structs. I'm at a point that the compiler doesn't give any errors, but the sort function doesn't give the right output yet. The two structures and the two compare functions are defined as follows:

typedef struct Query {int day, rank;} Query;  

typedef struct Event {int day, frame; char action;} Event;

int compEvents (const void *a, const void *b) {
  return (*(Event**)a)->day - (*(Event**)b)->day;
}

int compQueries (const void *a, const void *b) {
  return (*(Query**)a)->day - (*(Query**)b)->day;
}

If I use qsort, everything works fine and the output is correct:

qsort (queries, size, sizeof(Query*), compQueries);

If I use a different mergesort for each type, and don't use the compare functions, everything works fine too:

void queryMerge(Query **arr, int left, int mid, int right) {
  Query **temp = newQueryArray(right-left+1);
  int i = left, j = mid + 1, t = 0;   
  while (i <= mid && j <= right) {
    if (arr[i]->day < arr[j]->day) temp[t++] = arr[i++];
    else temp[t++] = arr[j++];
  }
  while (i <= mid) temp[t++] = arr[i++];
  while (j <= right) temp[t++] = arr[j++];
  for (int i = left; i <= right; i++) arr[i] = temp[i-left];
  free(temp);
}

void querySort(Query **arr, int left, int right) { 
  if (left < right) {
    int mid = left + (right - left)/2;
    querySort(arr, left, mid);
    querySort(arr, mid+1, right);
    queryMerge(arr, left, mid, right);
  }
}

void eventMerge(Event **arr, int left, int mid, int right) {
  Event **temp = newEventArray(right-left+1);
  int i = left, j = mid + 1, t = 0;   
  while (i <= mid && j <= right) {
    if (arr[i]->day < arr[j]->day) temp[t++] = arr[i++];
    else temp[t++] = arr[j++];
  }
  while (i <= mid) temp[t++] = arr[i++];
  while (j <= right) temp[t++] = arr[j++];
  for (int i = left; i <= right; i++) arr[i] = temp[i-left];
  free(temp);
}

void eventSort(Event **arr, int left, int right) { 
  if (left < right) {
    int mid = left + (right - left)/2;
    eventSort(arr, left, mid);
    eventSort(arr, mid+1, right);
    eventMerge(arr, left, mid, right);
  }
}

However, if I try to use a generic mergesort that would work for both types just like qsort, it isn't working correctly, even though the compiler and valgrind have no complaints:

void merge(void *arr, int left, int mid, int right, int width, int (*comp)(const void*, const void*)) {
  void *temp = malloc((right - left + 1) * width);
  int i = left, j = mid + 1, t = 0;   
  while (i <= mid && j <= right) {
    if (comp((char*)arr + i*width, (char*)arr + j*width)) {
      memcpy((char*)temp + t*width, (char*)arr + i*width, width);
      i++; t++;
    } else {
      memcpy((char*)temp + t*width, (char*)arr + j*width, width);
      j++; t++;
    }
  }
  while (i <= mid) {
    memcpy((char*)temp + t*width, (char*)arr + i*width, width);
    i++; t++;
  }
  while (j <= right) {
    memcpy((char*)temp + t*width, (char*)arr + j*width, width);
    j++; t++;
  }
  for (int i = left; i <= right; i++) {
    memcpy((char*)arr + i*width, (char*)temp + (i - left)*width, width);
  }
  free(temp);
}

void mergeSort(void *arr, int left, int right, int width, int (*comp)(const void*, const void*)) { 
  if (left < right) {
    int mid = left + (right - left)/2;
    mergeSort(arr, left, mid, width, comp);
    mergeSort(arr, mid+1, right, width, comp);
    merge(arr, left, mid, right, width, comp);
  }
}

This is the way it is called:

mergeSort(queries, 0, size-1, sizeof(Query*), compQueries);

I tried different things to get the void pointers right, but I'm still not sure. Any ideas?

Answer 1

Your usage of comparison function is broken:

if (comp((char*)arr + i*width, (char*)arr + j*width)))

is the same as

if (comp((char*)arr + i*width, (char*)arr + j*width)) != 0)

while you need

if (comp((char*)arr + i*width, (char*)arr + j*width)) < 0)

With your code you will ignore which was larger but only if they are same. As a result you do not sort at all.

Adding the <0 fixes the sorting.

Note: Your specific function uses correct comparison result:

if (arr[i]->day < arr[j]->day)