Stooge Sort: An Un-popular sorting Algorithm

Hey!! today I’m sharing my learnings with you all.

I was in my graduate algorithm lecture, and our faculty came up with “Stooge Sort”. I haven’t heard of this sorting algorithm before. I get to know that with this algorithm we can get a complete understanding of recursion and unrolling.

Then after the lecture, I researched this algorithm and finds it interesting, after the research and completely understanding the algorithm, I thought it might be a great idea to write a small article on it.

I’m assuming that all the readers know why we use sorting and how important sorting is…

So now, the first question is “What is Stooge Sort” ??

So, Stooge sort is a sorting algorithm, used to sort a linear array having n number of elements. What it does is, recursively sorts the partitions of the array of 2/3rd size, and after sorting each partition, the complete array gets sorted. It is not much efficient algorithm, but this algorithm can help to get a better understanding of recursion.

The Procedure

If the size of the array = 2, it swaps A[0], A[1] if A [0] > A [1], or else it divides the whole array into two overlapping partitions each of size 2/3 of the number of elements in the array.

Fig 1. Array Partitions

From figure 1, we can see that there are three partitions in total, the size of these partitions is generally,

Fig 2. Relations between the partitions

We first recursively sort the first partition, then we sort the second partition, and then again, we sort the first partition,

Note: there can be a case in which the elements smaller than the first partition still lie in the overlapping area i.e. “v” partition, that is why, we sort the first partition again at the end.

After this step, our whole array gets sorted.

Let’s take an example to explain the note mentioned above,

Fig 3. Example explaining the third recursive call

def StoogeSort(A):
    n = |A|
    # base case
    if (n == 2 && A[0] > A[1]):
        swap (A[0], A[1])
        return
    elif (n > 2):
        partition = math.ceil(2*n / 3)
        StoogeSort(A[0, partition - 1]);
        StoogeSort(A[n - partition, n - 1]);
        StoogeSort(A[0, partition - 1]);

As there are many recursive calls involved in this algorithm, that is why its complexity is a bit high, and it is even worse than the bubble sort.

The recurrence relation of this algorithm is,

Fig 4. Recurrence Relation of Stooge Sort

The “3” in the recurrence relation indicates that we are calling the function three times, and passing the partition of the array, and O (1) is for the swapping of two array elements.

After solving the recurrence relation, using master’s theorem, we get the time complexity as:

Fig 5. Time Complexity

It is even worse than the bubble sort in the worst case.

If we discuss the number of swaps involved in this algorithm, Hence, the worst case is all possible pair of the elements has swapped, at most C(n,2) times.

Let suppose, we take an array of size 10, A = [2, 4, 5, 3, 8, 6, 9, 7, 10, 1]

In this case, the size is greater than 2, then the base case fails and we go to else block,

Firstly, we find the partition(m) size using the formula ceil(2n/3),

m = ceil (2*10/3) = ceil (6.67) = 7                             
// why we take ceil value I’ll discuss later

from the algorithm above, we first call the StoogeSort(A[0…m-1]) = A [2,1,5,3,8,6,9], then the algorithm recursively calls itself and applies the partitions, and sorts them, after the final call, this partition gets sorted i.e., A = [2,3,4,5,6,8,9].

Then we make the second recursive call to StoogeSort (A [n-m…n-1]) = A [5,6,8,9,7,10,1], after applying the same steps, we get this array partition as A = [1,5,6,7,8,9,10].

Now, at this point, our complete array will look like this, A = [2,3,4,1,5,6,7,8,9,10], we can clearly see that our array is not completely sorted, so for that, we again recursively call the StoogeSort (A[0…m-1]).

After this, it is sure that we get the completely sorted array as

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Now the question arises, why do we take ceil value to make partitions in this algorithm?? Why this will not work for floor values?

So to answer this question, let's scroll a bit, and see the relation between the sizes of partitions x, y, and z in figure 2. So, if we take the floor value of 2n/3, then the relation breaks, and for this algorithm to work properly and sort the complete array, it should be satisfied.

Let’s understand this with an example.

Suppose we take an array of size 5, A = [ 1, 5, 4, 3, 2]

partition(m) = floor (2n/3) = floor (2*5/3) = floor (3.33) = 3

After applying the algorithm, the final array will look like this,

A = [1, 2, 4, 3, 5], which is not sorted. But if take the ceiling value here, the algorithm perfectly sorts this array.

Thanks a lot for sparing your time !!

References:

Stooge sort analysis

https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf