Get this book -> Problems on Array: For Interviews and Competitive Programming

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

- If the value at the start is larger than the value at the end, swap them.
- Recursively sort the first 2/3 part of the array.
- Recursively sort the last 2/3 part of the array.
- Again sort the firsty 2/3 part of the array.
- 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.