Недолуге сортування — це рекурсивний алгоритм сортування . Йому притаманна надзвичайно погана часова складність . Швидкість роботи алгоритму менша порівняно з оптимальними алгоритмами сортування, він повільніший за 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 }