Stooge Sort

Home » Projects » Sorting Algorithms » Exchange Sorts » Stooge Sort

Stooge Sort is an inefficient sorting algorithm named after The Three Stooges. It is inefficient in terms of time complexity and is primarily used for educational purposes or as a joke due to its impracticality for practical sorting tasks.

How Stooge Sort works

Stooge sort works with a simple process of splitting into 3rds. It takes the array and sorts the 2/3rds on the left, then the 2/3rds on the right, and then the 2/3rds on the left again. If the thirds of the array are larger than 1, then that sub-array is sorted recursively using

Example

Consider an array like this:

[4, 8, 5, 1, 6, 3, 7, 2, 0]

Then pick the first two thirds:

[4, 8, 5, 1, 6, 3][7, 2, 0]

This is our new sub-array. Now we need to sort it by splitting off the first two thirds and then again.

[[4, 8, 5], 1][6, 3][7, 2, 0]

Now that we’ve reached the size of 3, we can do some actual sorting. First compare the first two [4, 8] and do nothing because they’re in the right order. Then [8, 5] and swap them because they’re out of order. The final comparison of [4, 5] doesn’t get swapped.

[[4, 5, 8], 1][6, 3][7, 2, 0]

Next we incorporate the 1 into our sub-array. Since the array is of size 4, we sort the first three items (which we just did) then the last 3, then this first three again.

[4, [1, 5, 8]][6, 3][7, 2, 0]
[[1, 4, 5], 8][6, 3][7, 2, 0]
[[1, 4, 5, 8][6, 3]][7, 2, 0]

Next we integrate the [6, 3] using the same kind of method. The first 2/3rds are already sorted (first 4 items), so we sort items 2-5 as the second 3rd, then again the first third.

[[1, 4, [5, 8, 6, 3]]][7, 2, 0]
[[1, 4, [3, 5, 6, 8]]][7, 2, 0]
[[[1, 4, 3, 5], 6, 8]][7, 2, 0]
[[[1, 3, 4, 5], 6, 8]][7, 2, 0]
[1, 3, 4, 5, 6, 8][7, 2, 0]

The rest is just more iterations of the same process on different sections and sizes.

Visualisation

TBD

Time complexity

Stooge Sort uses comparisons and swaps in order to sort the array.

Comparisons

This has to be one of the most bizarre formulae I’ve had to work with. Stooge Sort is highly reliant on the length of the input array since adding a new layer of depth to the recursion creates a large bump in the amount of comparisons made, making it have a similar ‘step’ pattern to many Distribution Sorts.

That said, this is the formula for comparisons (orange line):

If you exclude the flooring wrapper and use only 0.92n^(log2(3)/log2(1.5)), then you get the grey line in the graph.

This exponent comprised of the quotient with two logs is equal to approx 2.709. This means that it still has quadratic complexity like Bubble Sort, but the exponent is a bit larger which makes it a lot slower.

Swaps

Swaps on the other hand are very straight forward. Since the Stooge Sort algorithm only exchanges adjacent elements, it is practically equivalent to the swap complexity of Bubble Sort (without the P discount).

Distribution

This is how the comparisons and swaps are distributed for this sorting algorithm of size 100 for 100,000 sorts.

Mode: 177,147
Mean: 177,147
Std dev: 0
Max: 177,147
Min: 177,147

Mode: 2,550
Mean: 2,568
Std dev: 167
Max: 3,280
Min: 1,866

The comparison distribution is very simple, there is only one possible result for any particular size of stooge sort. Though as the time complexity graph shows, there is only one possible comparison complexity for many similar list sizes.

The distribution for swaps is more unremarkable still; it’s just a standard normal distribution in the same vein as Bubble sort, but with a slightly higher mean due to the ever-present permutation pre-solver P.

C code

void stooge_sort_recursive(int *p, int len, int l) {
	int chunk; 
	// If length is greater than 2, reduce array width and do another Stooge Sort
	if (len > 2) {
		// Reduce length of array to a shorter one with this formula
		chunk = (len / 3) * 2 + (len % 3);
		// Recursively invoke Stooge Sort for the 1st 2/3rds, then the last 2/3rds then the 1st 2/3rds again
		stooge_sort_recursive(p, chunk, l+1);
		stooge_sort_recursive(&p[len/3], chunk, l+1);
		stooge_sort_recursive(p, chunk, l+1);
	} else {
		// Check if they need swapping again
		if (is_greater_than_p(&p[0], &p[len-1])){
			swap(&p[0], &p[len-1]);
		}
	}
}