Stooge Sort

Stooge sort is a recursive sorting algorithm with very poor efficiency. It repeatedly sorts overlapping parts of the array. The algorithm has theoretical interest but no practical use.

Problem

Given a sequence $A$ of length $n$, reorder it such that

$$ A[0] \le A[1] \le \cdots \le A[n-1] $$

Algorithm

For a subarray $A[l..r]$:

1. If the first element is greater than the last, swap them

2. If the size is greater than 2, recursively sort:

   • the first $\frac{2}{3}$ of the array
   • the last $\frac{2}{3}$ of the array
   • the first $\frac{2}{3}$ again

stooge_sort(A, l, r):
    if A[l] > A[r]:
        swap(A[l], A[r])

    if r - l + 1 > 2:
        t = (r - l + 1) // 3

        stooge_sort(A, l, r - t)
        stooge_sort(A, l + t, r)
        stooge_sort(A, l, r - t)

Example

Let

$$ A = [2, 1, 3] $$

Step 1:

Swap first and last if needed → no change

Recursive calls:

• sort first 2 elements → [1,2,3]
• sort last 2 elements → [1,2,3]
• sort first 2 elements again

Final result:

$$ [1,2,3] $$

Correctness

The recursive structure ensures that elements are repeatedly compared and corrected across overlapping regions. Over time, all inversions are eliminated. However, this process is highly redundant.

Complexity

The recurrence is:

$$ T(n) = 3T\left(\frac{2n}{3}\right) + O(1) $$

This solves to:

$$ T(n) = O(n^{\log_{3/2} 3}) \approx O(n^{2.71}) $$

This is worse than $O(n^2)$.

Space complexity:

$$ O(\log n) $$

due to recursion depth.

Properties

• in-place
• not stable
• extremely inefficient
• overlapping recursive structure

When to Use

Stooge sort has no practical use. It is studied as an example of inefficient recursion and as a contrast to efficient divide-and-conquer algorithms.

Implementation

def stooge_sort(a, l, r):
    if a[l] > a[r]:
        a[l], a[r] = a[r], a[l]

    if r - l + 1 > 2:
        t = (r - l + 1) // 3

        stooge_sort(a, l, r - t)
        stooge_sort(a, l + t, r)
        stooge_sort(a, l, r - t)

func StoogeSort[T constraints.Ordered](a []T, l, r int) {
    if a[l] > a[r] {
        a[l], a[r] = a[r], a[l]
    }

    if r-l+1 > 2 {
        t := (r - l + 1) / 3

        StoogeSort(a, l, r-t)
        StoogeSort(a, l+t, r)
        StoogeSort(a, l, r-t)
    }
}