Summary

Stooge Sort is a recursive algorithm notable for its exceptionally poor performance. Its name is a reference to The Three Stooges. The algorithm divides the array into two overlapping sub-arrays of size 2/3, sorts them recursively, and then re-sorts the first 2/3 to ensure the elements are in their correct final positions. It serves as an excellent academic example of how a seemingly plausible 'divide and conquer' strategy can lead to a very inefficient solution.

How it Works

• If the value at the start of the sub-array is larger than the value at the end, swap them.

• If the current sub-array has three or more elements, proceed. Otherwise, the sub-array is sorted.

• Recursively call Stooge Sort on the initial two-thirds of the sub-array.

• Recursively call Stooge Sort on the final two-thirds of the sub-array.

• Recursively call Stooge Sort on the initial two-thirds of the sub-array again to fix the placement of elements that may have moved from the final third into the initial third.