Select Page

# Program for Stooge Sort using Python

by | Jun 28, 2021 | Python Programs

## 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])```

## 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.