неустойчивая сортировка

[Missir]

Есть такой алгоритм сортировки слиянием. Пишут, что это устойчивый алгоритм, но данная реализация неустойчива. Порядок равных элементов в нём меняется непредсказуемо. Можно это как то исправить? Пробовал менять "<" на "<=" но эффекта никакого нет. Что можно ещё попробовать?

Используется синтаксис C

void mgsrt64(uint64_t *x, int64_t n)
{ // сортировка слиянием для массива uint64
  int64_t i, j, k, u, v, g, res, len;
  
  len=n;
  for (i=0; i<n; i++){prt[i]=-1; idx[i]=i;}                     
  while (len!=1) 
  {  i=0; j=0; 
     while (j<(len/2))
     { if (x[idx[i]]<x[idx[i+1]]) {u=idx[i]; g=idx[i+1]; idx[j]=u;}
       else {u=idx[i+1]; g=idx[i]; idx[j]=u;}   
       k=prt[u]; 
       while ((k!=-1) && (g!=-1))
         if (x[k]<x[g]){u=k; k=prt[k];}             
         else {prt[u]=g; u=g; v=prt[g]; prt[g]=k; g=v;}              
       if (k==-1) prt[u]=g;         
       i+=2; j++;          
     }
     res=len%2; if (res==1) idx[j]=idx[i]; len=len/2+res;                       
  }
  k=idx[0]; for (i=1; i<n; i++) {k=prt[k]; idx[i]=k;}
}
 

[Geen]

Missir в сообщении #1650649 писал(а):

Порядок равных элементов в нём меняется непредсказуемо

А как Вы это установили?

Missir в сообщении #1650649 писал(а):

Пробовал менять "<" на "<=" но эффекта никакого нет. Что можно ещё попробовать?

Переписать реализацию заново.

-- 19.08.2024, 08:46 --

Missir в сообщении #1650649 писал(а):

но данная реализация неустойчива.

А это вообще, реализация, сортировки, слиянием?

[StepV]

Missir в сообщении #1650649 писал(а):

Что можно ещё попробовать?

Стандартный совет. Прогоните процедуру в отладчике. Проходите построчно цикл и смотрите, как меняются элементы массива.

[Missir]

StepV, благодаря Вам всё таки нашел причину, прогнал на нескольких примерах и нашел ошибку, причём очень похожие фрагменты сортируются по разному:
47, 55, 57, 60, 64, 64, 60, 46 - меняет местами 60
46, 54, 57, 60, 64, 64, 60, 47 - сортирует правильно.

Сортировка этих фрагментов в итоге сводится к слиянию
47, 55, 57, 60 и 46, 60, 64, 64 в первом случае, и
46, 54, 57, 60 и 47, 60, 64, 64 во втором.

В первом случае алгоритм берёт 2 блок и сливает его с первым, в этом месте и возникает ошибка, т.к. 60 меняются местами.
Во втором случае он сливает первый блок со вторым и ошибки нет.

Получается, в первом условии нужно использовать "<=", а второе условие зависит от результата проверки первого условия, т.е.

Используется синтаксис C

if (x[idx[i]]<=x[idx[i+1]])
 

Если оно выполняется, т.е. сливается предыдущий и последующий блоки, то тоже нужно брать "<=", и всё должно работать корректно.,
но как поступать в противном случае пока не ясно. Первое, что приходит в голову, брать "<".

-- 19.08.2024, 20:06 --

В общем подправил, теперь похоже стало работать корректно, по крайней мере ни одной ошибки больше не наблюдалось.