Size:8

Overview & Concept

Stooge Sort is a recursive sorting algorithm with an unusually high time complexity of O(n^(log 3 / log 1.5)) ≈ O(n^2.7095). It sorts an array by comparing endpoints, swapping them if out of order, and recursively sorting the first 2/3, the last 2/3, and the first 2/3 again.

How It Works

Endpoint Comparison: If the first element is greater than the last element, swap them.

Recursive Partitioning: If the partition length is 3 or greater, calculate third length t = floor(length / 3).

Overlapping Recursion 1: Recursively sort the first 2/3 (indices low to high - t).

Overlapping Recursion 2: Recursively sort the last 2/3 (indices low + t to high).

Overlapping Recursion 3: Recursively sort the first 2/3 again to ensure correct overall ordering.

Step-by-Step Execution

1. Compare EndpointsIf A[low] > A[high], swap A[low] and A[high].

2. Check Base CaseIf high - low + 1 < 3, return.

3. Calculate Third Sizet = floor((high - low + 1) / 3).

4. Overlapping RecursionRecurse on [low..high - t], then [low + t..high], then [low..high - t] again.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(n^2.71)	O(n^2.71)	O(n^2.71)	O(log n)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure stoogeSort(A, low, high):
  if A[low] > A[high]: swap(A[low], A[high])
  if high - low + 1 >= 3:
    t = floor((high - low + 1) / 3)
    stoogeSort(A, low, high - t)
    stoogeSort(A, low + t, high)
    stoogeSort(A, low, high - t)

Algorithmic Invariants

Two-Thirds Overlap Invariant: The largest elements are guaranteed to move into the upper third after the first two recursive calls, and the final call settles the lower two thirds.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Fascinating theoretical recursive structure used in complexity analysis education.
•In-place sort requiring no auxiliary memory beyond the recursion stack.

Trade-offs & Limitations

•Extremely slow: O(n^2.71) time complexity is slower than even Bubble Sort.
•Deep recursion call stack O(log n).

Real-World Applications

Algorithm Complexity Benchmarking

Used as an adversarial pedagogical example when teaching Master Theorem and recursion trees.

Decision Guide: When to Use

Ideal Scenarios

✓Strictly for theoretical computer science education and recursive analysis.

Consider Alternatives When

✕In all production applications.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Merge Sort Quick Sort Bubble Sort