Python Program for Stooge Sort

The Stooge sort is a horribly inefficient recursive sorting algorithm. In this tutorial, we are going to sort an array with help of the Stooge Sort algorithm.

Stooge Sort - Basic Introduction

The stooge sort algorithm swaps the top and bottom items, then sorts the bottom two-thirds, top two-thirds, and bottom two-thirds again (recursively). We can summarize stoop sort in the following methods:

• Swap the values if the value at index 0 is larger than the value at the final index
• Stooge sorts the first 2/3rd of the array recursively.
• Sort the final 2/3 of the array with Stooge.
• To double-check, Stooge sorts the first two-thirds again.

Look at the diagram below for a better understanding:

Algorithm

As of now, we have a rough understanding of how the stooge sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Create a function stooge_sort()
2. Pass 3 parameter array, length, a
3. Swap, If the first element is smaller than last
4. Mark condition if there are more than 2 elements in the array
5. Recursively sort first 2/3 elements
6. Recursively sort last 2/3 elements
7. Check, if again sort is required
8. If required follow step 5
9. If not required return sorted array
10. Print the sorted array

Program for Stooge Sort

As discussed above in the algorithm, let us now dive into the programming part of the stooge sort operation influenced by the algorithm.

def stooge_sort(array, length, a):
	if length >= a:
		return

	if array[length]>array[a]:
		b = array[length]
		array[length] = array[a]
		array[a] = b

	if a-length+1 > 2:
		b = (int)((a-length+1)/3)

		stooge_sort(array, length, (a-b))

		stooge_sort(array, length+b, (a))

		stooge_sort(array, length, (a-b))

# driver code
array = [2, 4, 5, 3, 1]
print("The original array is:", array)
l = len(array)
stooge_sort(array, 0, l-1)
print("The sorted array is:", array)

The original array is: [2, 4, 5, 3, 1]
The sorted array is: [1, 2, 3, 4, 5]

Conclusion

In this tutorial, we have performed a stooge sort operation in python to sort an array. It is an unstable program having the time complexity of the stooge sort is O(n^{log(3) /log(1.5)}) and the space complexity is O(n).