Недолуге сортування

Недолуге сортування — це рекурсивний алгоритм сортування . Йому притаманна надзвичайно погана часова складність O(n^{log 3 / log 1.5} ) = O(n^2.7095...). Швидкість роботи алгоритму менша порівняно з оптимальними алгоритмами сортування, він повільниший за Bubble sort, що є канонічним прикладом досить неефективного алгоритму сортування. Однак він ефективніший, ніж Slowsort . Назва походить від комедійного тріо The Three Stooges.

Алгоритм визначається наступним чином:

• Якщо значення на початку списку більше значення в кінці списку, то поміняти їх місцями.
• Якщо в списку є 3 або більше елементів:
  • Рекусивно застосувати алгоритм до перших 2/3 списку
  • Рекусивно застосувати алгоритм до останніх 2/3 списку
  • Знову рекусивно застосувати алгоритм до перших 2/3 списку

При обчисленні кількості елементів при вираховуванні 2/3 списку, важливо округлювати вгору, наприклад, 2/3 від 5 має бути 4, а не 3, оскільки в іншому випадку для певних даних сортування може бути невдалим.

Реалізація

 function stoogesort(array L, i = 0, j = length(L)-1){
   if L[i] > L[j] then   
     L[i] ↔ L[j]      
   if (j - i + 1) > 2 then   
     t = floor((j - i + 1) / 3)
     stoogesort(L, i , j-t) 
     stoogesort(L, i+t, j)  
     stoogesort(L, i , j-t) 
   return L
 }