Stooge sort

O(n^2.71)

Stooge sort swaps the ends if they're out of order, then recursively sorts the first two-thirds, the last two-thirds, and the first two-thirds again. It's correct but gloriously inefficient — about O(n^2.71) — making it a textbook example of how a plausible-looking recursion can be terrible.

Array
Edit the input and press Play

How it works

  1. If the first element is bigger than the last, swap them.
  2. Recursively sort the first two-thirds of the range.
  3. Recursively sort the last two-thirds.
  4. Recursively sort the first two-thirds once more.

Pseudocode

1stoogeSort(a, lo, hi):              # O(n^2.71)2  if a[lo] > a[hi]: swap(a[lo], a[hi])3  if hi - lo + 1 > 2:4    t ← (hi - lo + 1) / 35    stoogeSort(a, lo, hi-t)          # first two-thirds6    stoogeSort(a, lo+t, hi)          # last two-thirds7    stoogeSort(a, lo, hi-t)          # first two-thirds again