Stooge Sort

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)

Stooge Sort is an intentionally inefficient sorting algorithm, names after The Three Stooges.

It takes a look at the first and last elements. If they are out of order, it swaps them. Then, it calls itself on the first two-thirds of the array. Then it calls itself on the second two-thirds of the array. Then it calls itself again on the first two-thirds. It has three recursive calls in each call.

Let's say you have the infamous array:

4, 1, 5, 2, 3

Stooge Sort compares the first and last elements. They are out of order, so it swaps them.

3, 1, 5, 2, 4

It then calls itself on the first two-thirds of the array, which is the first three elements.

3, 1, 5

It checks the first and last elements, which are equal, so it calls itself on the first two-thirds.

3, 1

The first and last elements are out of order, so it swaps them.

1, 3

The function returns to the previous call because it cannot multiply 2 by two-thirds.

1, 3, 5

This call is now on its second part, where it calls itself on the second two-thirds (the second through third elements).

3, 5

Seeing as they are in order, it returns.

1, 3, 5

It now calls itself again on the first two-thirds.

1, 3

Seeing as they are in order, it returns.

1, 3, 5

Now this routine also returns to the one below it on the call stack.

1, 3, 5, 2, 4

This now calls itself on the second two-thirds of the array, the third through the fifth elements.

5, 2, 4

It checks the first and last elements, which are out of order, so it swaps them.

4, 2, 5

It then calls itself on the first two-thirds, which are the first two elements.

4, 2

It checks the first and last elements, which are out of order, so it swaps them.

2, 4

Then it returns to the previous subroutine on the call stack.

2, 4, 5

Now it calls itself on the second two-thirds, the second through third elements.

4, 5

The first and last elements are in order, so it returns.

2, 4, 5

It calls itself again on the first two-thirds.

2, 4

There is nothing to swap with the first and last elements, so it returns.

2, 4, 5

Now it returns to the first call.

1, 3, 2, 4, 5

Now this level is on its last recursive call. It calls itself for the second time on the first two-thirds, the first through ** third** elements.

1, 3, 2

It checks the first and last elements, which are fine. It then calls itself on the first two-thirds.

1, 3

The first and last elements are in order, so it returns.

1, 3, 2

Then it calls itself on the second two-thirds.

3, 2

The first and last elements are out of order, so it swaps them.

2, 3

It returns to the previous method call.

1, 2, 3

Now it calls itself again on the first two-thirds.

1, 2

The first and last elements are fine. It returns.

1, 2, 3

This also returns to the first method call.

1, 2, 3, 4, 5

The array is now sorted. Yes, it is highly inefficient, swapping only the first and last elements.