Stooge Sort Program with Explanation and Code

2025-11-19 stooge sort recursive sorting inefficient sorting algorithm funny algorithms python stooge sort c stooge sort php stooge sort javascript stooge sort csharp stooge sort educational sorting methods

Stooge Sort is a famously inefficient recursive sorting algorithm that repeatedly sorts overlapping two-thirds of the array. This page explains how it works and provides complete code examples in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Stooge Sort?

Stooge Sort is a highly inefficient and humorous sorting algorithm known for its extremely poor performance. It works by recursively sorting the initial two-thirds of the array, the final two-thirds of the array, and again the initial two-thirds. Although it is easy to understand, Stooge Sort is mainly used for theoretical or educational purposes due to its terrible time complexity.

Steps to Solve

  1. If the first element is greater than the last element, swap them.
  2. If the array has more than two elements:
    • Compute the length of two-thirds of the array.
    • Recursively sort the first two-thirds.
    • Recursively sort the last two-thirds.
    • Recursively sort the first two-thirds again.
  3. Continue recursion until the entire array becomes sorted.
  4. Return the sorted array.

Key Points

  • One of the slowest sorting algorithms ever created.
  • Time complexity: O(n2.7095) — extremely slow.
  • Highly recursive and inefficient.
  • Used only for academic interest, not practical use.
  • Simple to implement but disastrously slow for large inputs.

Program Code


def stooge_sort(arr, l, h):
    if arr[l] > arr[h]:
        arr[l], arr[h] = arr[h], arr[l]

    if h - l + 1 > 2:
        t = (h - l + 1) // 3
        stooge_sort(arr, l, h - t)
        stooge_sort(arr, l + t, h)
        stooge_sort(arr, l, h - t)

arr = list(map(int, input("Enter numbers: ").split()))
stooge_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)
      

#include <stdio.h>

void stoogeSort(int arr[], int l, int h) {
    if (arr[l] > arr[h]) {
        int temp = arr[l];
        arr[l] = arr[h];
        arr[h] = temp;
    }

    if (h - l + 1 > 2) {
        int t = (h - l + 1) / 3;
        stoogeSort(arr, l, h - t);
        stoogeSort(arr, l + t, h);
        stoogeSort(arr, l, h - t);
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    stoogeSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function stoogeSort(arr, l, h) {
  if (arr[l] > arr[h]) {
    [arr[l], arr[h]] = [arr[h], arr[l]];
  }

  if (h - l + 1 > 2) {
    let t = Math.floor((h - l + 1) / 3);
    stoogeSort(arr, l, h - t);
    stoogeSort(arr, l + t, h);
    stoogeSort(arr, l, h - t);
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
stoogeSort(arr, 0, arr.length - 1);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void StoogeSort(int[] arr, int l, int h) {
        if (arr[l] > arr[h]) {
            int temp = arr[l];
            arr[l] = arr[h];
            arr[h] = temp;
        }

        if (h - l + 1 > 2) {
            int t = (h - l + 1) / 3;
            StoogeSort(arr, l, h - t);
            StoogeSort(arr, l + t, h);
            StoogeSort(arr, l, h - t);
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        StoogeSort(arr, 0, arr.Length - 1);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function stoogeSort(&$arr, $l, $h) {
    if ($arr[$l] > $arr[$h]) {
        $temp = $arr[$l];
        $arr[$l] = $arr[$h];
        $arr[$h] = $temp;
    }

    if ($h - $l + 1 > 2) {
        $t = intval(($h - $l + 1) / 3);
        stoogeSort($arr, $l, $h - $t);
        stoogeSort($arr, $l + $t, $h);
        stoogeSort($arr, $l, $h - $t);
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
stoogeSort($arr, 0, count($arr) - 1);

echo "Sorted array: " . implode(" ", $arr);

?>
1