Stooge Sort

Recursively sorts first 2/3, last 2/3, then first 2/3 again. Named after The Three Stooges. Extremely slow — purely educational.

Best O(n^2.71) Avg O(n^2.71) Worst O(n^2.71) Space O(log n) Stable No In-place Yes Comparison-based

How it works

Recursively sorts first 2/3, last 2/3, then first 2/3 again. Named after The Three Stooges. Extremely slow — purely educational.

Implementation

      
 function stoogeSort(arr, lo = 0, hi = arr.length - 1) {
  if (arr[lo] > arr[hi])
    [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
  if (hi - lo + 1 > 2) {
    let t = Math.floor((hi - lo + 1) / 3);
    stoogeSort(arr, lo, hi - t);
    stoogeSort(arr, lo + t, hi);
    stoogeSort(arr, lo, hi - t);
  }
} def stooge_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if arr[lo] > arr[hi]:
        arr[lo], arr[hi] = arr[hi], arr[lo]
    if hi - lo + 1 > 2:
        t = (hi - lo + 1) // 3
        stooge_sort(arr, lo, hi - t)
        stooge_sort(arr, lo + t, hi)
        stooge_sort(arr, lo, hi - t) void stoogeSort(vector<int>& arr, int lo, int hi) {
  if (arr[lo] > arr[hi]) swap(arr[lo], arr[hi]);
  if (hi - lo + 1 > 2) {
    int t = (hi - lo + 1) / 3;
    stoogeSort(arr, lo, hi - t);
    stoogeSort(arr, lo + t, hi);
    stoogeSort(arr, lo, hi - t);
  }
} void StoogeSort(int[] arr, int lo, int hi) {
  if (arr[lo] > arr[hi])
    (arr[lo], arr[hi]) = (arr[hi], arr[lo]);
  if (hi - lo + 1 > 2) {
    int t = (hi - lo + 1) / 3;
    StoogeSort(arr, lo, hi - t);
    StoogeSort(arr, lo + t, hi);
    StoogeSort(arr, lo, hi - t);
  }
} void stoogeSort(int arr[], int lo, int hi) {
  if (arr[lo] > arr[hi]) {
    int t = arr[lo]; arr[lo] = arr[hi]; arr[hi] = t;
  }
  if (hi - lo + 1 > 2) {
    int t = (hi - lo + 1) / 3;
    stoogeSort(arr, lo, hi - t);
    stoogeSort(arr, lo + t, hi);
    stoogeSort(arr, lo, hi - t);
  }
} 