# Stooge Sort

# 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

```id="k4p8x1"
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

```id="m9x2q4"
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)
```

```id="z3k7v1"
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)
    }
}
```