Стабильная сортировка слиянием C

Я пишу простую функцию сортировки слиянием для сортировки на основе заданной функции compar : 

void merge(int left, int mid, int right, int(*compar)(const void *, const void *))
{
  // sublist sizes
  int left_size = mid - left + 1;
  int right_size = right - mid;

  // counts
  int i, j, k;

  // create left and right arrays
  B *left_list = (B*) malloc(left_size*sizeof(B));
  B *right_list = (B*) malloc(right_size*sizeof(B));

  // copy sublists, could be done with memcpy()?
  for (i = 0; i < left_size; i++)
    left_list[i] = list[left + i];

  for (j = 0; j < right_size; j++)
    right_list[j] = list[mid + j + 1];

  // reset counts
  i = 0; j = 0;

  for (k = left; k <= right; k++)
  {
    if (j == right_size)
      list[k] = left_list[i++];
    else if (i == left_size)
      list[k] = right_list[j++];
    // here we call the given comparision function
    else if (compar(&left_list[i], &right_list[j]) < 0)
      list[k] = left_list[i++];
    else
      list[k] = right_list[j++];
  }
}

void sort(int left, int right, int(*compar)(const void *, const void *))
{
  if (left < right)
  {
    // find the pivot point
    int mid = (left + right) / 2;

    // recursive step
    sort(left, mid, compar);
    sort(mid + 1, right, compar);

    // merge resulting sublists
    merge(left, mid, right, compar);
  }
}

Затем я вызываю это несколько раз в одном и том же массиве list, используя различные функции сравнения. Я нахожу, что сортировка стабильна для первого вызова, но после этого я вижу, что элементы меняются местами, даже если они равны.

Может ли кто-нибудь предположить причину такого поведения?
2 2
sorting mergesort

2 ответа:

Я не уверен, что это поможет, но попробуйте изменить эту строку: 

compar(&left_list[i], &right_list[j]) < 0

К этому: 

compar(&left_list[i], &right_list[j]) <= 0
Это сделает его таким, что, если они уже равны, он делает первое действие, которое (надеюсь) сохранит стабильность, а не перемещает вещи вокруг.

Это всего лишь предположение.

3

Я думаю, что вы неправильно определили свои размеры 

int left_size = mid - left;

И, как указывает арасмуссен, вам нужно отдать предпочтение левому списку, чтобы сохранить стабильность 

compar(&left_list[i], &right_list[j]) <= 0

В дополнение ко всему этому, вы не вызываете free После того, как malloc-ING вспомогательные списки. Это не приведет к тому, что алгоритм вернет неверные результаты, но приведет к необратимому увеличению использования памяти вашей программы при каждом вызове функции сортировки.

1