Dark Mode On/Off

# 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(nlog(3) /log(1.5)) and the space complexity is O(n).

Want to learn coding?
Try our new interactive courses.
Over 20,000+ students enrolled.