Stooge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Stooge Sort

An educational recursive sorting algorithm: achieves correct sorting by recursively sorting the first two-thirds, last two-thirds, and first two-thirds of the list again.

How it works

Stooge Sort is a recursive divide-and-conquer algorithm. It is highly famous in computer science education because of its terrible performance and unusual fractional division. Here is the recursive procedure:

1. Compare the elements at the `start` and `end` indices. If the first element is larger than the last, swap them.
2. If there are 3 or more elements in the current sub-segment:
   • Let \(t = \lfloor (end - start + 1) / 3 \rfloor\) represent one-third of the current range size.
   • **First two-thirds:** Recurse on the first two-thirds of the list: `stoogeSort(A, start, end - t)`.
   • **Last two-thirds:** Recurse on the last two-thirds of the list: `stoogeSort(A, start + t, end)`.
   • **First two-thirds again:** Recurse on the first two-thirds again: `stoogeSort(A, start, end - t)` to ensure no large elements migrated back.

Complexity

Interactive visualization

Pseudocode

procedure stoogeSort(A, start, end):
  if A[start] > A[end]:
    swap(A[start], A[end])
    
  if (end - start + 1) >= 3:
    t ← floor((end - start + 1) / 3)
    stoogeSort(A, start, end - t)   # First two-thirds
    stoogeSort(A, start + t, end)   # Last two-thirds
    stoogeSort(A, start, end - t)   # First two-thirds again

JavaScript implementation

function stoogeSort(arr, start = 0, end = arr.length - 1) {
  if (arr[start] > arr[end]) {
    [arr[start], arr[end]] = [arr[end], arr[start]];
  }
  
  if (end - start + 1 >= 3) {
    const t = Math.floor((end - start + 1) / 3);
    stoogeSort(arr, start, end - t);
    stoogeSort(arr, start + t, end);
    stoogeSort(arr, start, end - t);
  }
  return arr;
}

Pros and cons

When (not) to use it

• Theoretical Classroom Studies: Perfect for illustrating recursive complexity analysis and mathematical proofs.
• Production Code: Never! Even for small arrays, Insertion Sort or Bubble Sort is significantly faster.