Stooge Sort

Reading time: 25 minutes | Coding time: 5 minutes

Stooge Sort is a recursive sorting algorithm. It is inefficient but interesting sorting algorithm. It divides the array into two overlapping parts (2/3 each). Then it performs sorting in first 2/3 part and then it performs sorting in last 2/3 part. After that, sorting is done on first 2/3 part to ensure the array is sorted.

The key idea is that sorting the overlapping part twice exchanges the elements between the other two sections accordingly.

Algorithm

1. If the value at the start is larger than the value at the end, swap them.
2. Recursively sort the first 2/3 part of the array.
3. Recursively sort the last 2/3 part of the array.
4. Again sort the firsty 2/3 part of the array.
5. The array becomes finally sorted.

Example

Input array: 2 4 5 3 1
Output array: 1 2 3 4 5

Step1:

Initially, First and last element is compared and if last is greater thanfirst then they are swapped.

1 4 5 3 1

Step 2:

Now, recursively sort initial 2/3rd of the elements.

Recursive sort 1st 2/3 elements (3): [1 4 5] 3 2
1 4 5 3 2

Step3:

Then, recursively sort last 2/3rd of the elements.

Recursive sort last 2/3 elements (3): 1 3 [4 5 2]
1 3 2 4 5

Step 4:

Again, sort the initial 2/3rd of the elements to confirm final data is sorted.

1 2 3 4 5

Pseudo Code

Following is the pseudo code for above algorithm:

StoogeSort(A, i, j)
if A[i]>A[j]
   then swap A[i] and A[j]
if i+1>=j
   then return
k=[(j-i+1)/3]
Stoogesort(A, i, j-k)
Stoogesort(A, i-k, j)
Stoogesort(A, i, j-k)

Implementation

Following code is the C++ implementation of above algorithm:

#include <bits/stdc++.h> 
using namespace std; 
void stoogesort(int arr[], int l, int h) 
{ 
    if (l >= h) 
        return; 
    if (arr[l] > arr[h]) 
        swap(arr[l], arr[h]); 
    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 arr[] = { 2, 4, 5, 3, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]);  
    stoogesort(arr, 0, n - 1); 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
    return 0; 
} 

Complexity Analysis

• Average time complexity - O(n ^ log(3) /log(1.5))
• Best-Case time complexity - O(n ^ log(3) /log(1.5))
• Worst-Case time complexity - O(n ^ log(3) /log(1.5))
• Worst-case space complexity - O(n)

Asymptotic time complexity analysis is straightforward. The algorithm first does constant time computation on lines 2–6 of pseudo code and then recursively calls itself, each time on an array whose size is 2/3 of the original array's size. So, the time complexity of above algorithm is given by:** O(n ^ log(3) /log(1.5))**

It is an inefficient sorting algortithm and is even slower than bubble sort but brings in a new idea of sorting overlapping sections to sort entire sequence.