Skip to main content

Stooge Sort Algorithm

What is the Stooge Sort Algorithm?

Stooge Sort is a simple and recursive sorting algorithm. It is known for its high time complexity and is mostly used for educational purposes to understand recursive sorting techniques.

Algorithm Steps

  1. Base Case:

    • If the array has only one element or the first element is less than or equal to the last element, return.
  2. Swapping:

    • If the first element is greater than the last element, swap them.
  3. Recursive Sort:

    • Recursively sort the first two-thirds of the array.
    • Recursively sort the last two-thirds of the array.
    • Recursively sort the first two-thirds of the array again.

Complexity Analysis

  • Time Complexity: O(nlog32)O(n^{\log_3 2}) which is approximately O(n2.7095)O(n^{2.7095}).
  • Space Complexity: O(n)O(n) due to the recursive call stack.

Example

Given an unsorted array:

array = [4, 3, 2, 1]

Using the Stooge Sort Algorithm:

  • Sort the first two-thirds: [4, 3, 2] -> [3, 4, 2] -> [3, 2, 4] -> [2, 3, 4]
  • Sort the last two-thirds: [3, 2, 1] -> [2, 1, 3] -> [1, 2, 3]
  • Sort the first two-thirds again: [4, 3, 2] -> [3, 4, 2] -> [3, 2, 4] -> [2, 3, 4]
  • The array becomes [1, 2, 3, 4].

Implementation

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

# Swap if the first element is greater than the last element
if arr[l] > arr[h]:
arr[l], arr[h] = arr[h], arr[l]

# Recursively sort the first two-thirds, last two-thirds, and first two-thirds again
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)

# Example usage:
array = [4, 3, 2, 1]
stooge_sort(array, 0, len(array) - 1)
print(array) # Output: [1, 2, 3, 4]

Conclusion

Stooge Sort is a straightforward but inefficient sorting algorithm. It is not practical for large datasets due to its high time complexity but can be useful for educational purposes to understand recursive sorting techniques.