Introduction

The stooge sort algorithm is the recursive algorithm. Our task is to sort the given array element using stooge sort.

Program

def sort(arr,first,last):
    if first >= last:
        return
# Compare first and last element and swap if required
    if arr[first]>arr[last]:
        temp = arr[first]
        arr[first] = arr[last]
        arr[last] = temp
    if last-first+1 > 2:
        temp = (int)((last - first + 1)/ 3)
# Sort first 2/3 elements
        sort(arr, first, (last - temp))
# Sort last 2/3 elements
        sort(arr, first + temp, (last))
# Sort first 2/3 elements
        sort(arr, first, (last - temp))
       
ip_arr = [9, 4, 1, 2]
sort(ip_arr, 0, len(ip_arr)-1)
print("The sorted array is :")
for i in range(0, len(ip_arr)):
    print(ip_arr[i])

Output

Explanation

In stooge sort, the array is divided into 2/3 parts. The steps followed in the above program are:

• We take the first element of the array and compare it to the last element. If required the values are swapped.
• Recursively we are sorting the first 2/3 elements of the array.
• Then, recursively we will sort the last 2/3 elements of the array.
• At last again we will sort the first 2/3 elements to check the elements are sorted
• The sorted array is returned.