**Stooge Sort:**

Stooge sort is a recursive sorting method with high time complexity. The algorithm’s execution time is longer than that of the Bubble sort. It is, though, more efficient than slow sorting.

**Algorithm:**

- If the value in the first place is greater than the value in the last position, swap them.
- If the list contains three or more elements, then

- To begin, Stooge sorts the first two-thirds of the list.
- Second, Stooge sorts the final two-thirds of the list.
- Finally, Stooge sorts the first two-thirds of the list once more.

**Steps:**

The array is first given to the function, which compares the first and last elements and swaps them if the first element is smaller.

Next, we assess the array’s size; if the size is greater than two, the array’s sections are called recursively to sort the first, last, and first two-thirds(2/3) of the array.

Finally, simply show the sorted array on the window.

**Examples:**

**Example1:**

**Input:**

Given List = [80, 90, 20, -10, 36]

**Output:**

The given list after sorting = [-10, 20, 36, 80, 90]

**Example2:**

**Input:**

Given List = [56, 43, -3, 100, 13]

**Output:**

The given list after sorting = [-3, 13, 43, 56, 100]

## Program for Stooge Sort in Python

### Method #1: Using Recursion (Static Input)

**Approach:**

- Give the list as static input and store it in a variable.
- Calculate the length of the given list using the len() function and store it in another variable.
- Take a variable and initialize it with the start value as 0.
- Take another variable and initialize it with the end value as the length of the list-1.
- Create a Recursive function say Stooge_Sorting() which accepts the given list, start value and end value as the arguments and returns the sorted list.
- Inside the function, check whether the list has any elements using the if conditional statement.
- If it is true then return.
- Check whether the element present at the start value of the list is greater than the element present at the end value using the if conditional statement.
- If it is true, then swap both of them.
- Check whether there are more than two elements using the if conditional statement.
- If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
- Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the function itself (Recursive Logic).
- Pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
- Pass the given list, start value, and end value as the arguments to the Stooge_Sorting() function.
- Print the given list after sorting.
- The Exit of the Program.

**Below is the implementation:**

# Create a Recursive function say Stooge_Sorting() which accepts the given list, # start value and end value as the arguments and returns the sorted list. def Stooge_Sorting(gvn_lst, strt_val, end_val): # Inside the function, check whether the list has any elements using the if # conditional statement. if strt_val >= end_val: # If it is true then return. return # Check whether the element present at the start value of the list is greater # than the element present at the end value using the if conditional statement. if gvn_lst[strt_val] > gvn_lst[end_val]: # If it is true, then swap both of them. gvn_lst[strt_val], gvn_lst[end_val] = gvn_lst[end_val], gvn_lst[strt_val] # Check whether there are more than two elements using the if conditional # statement. if end_val-strt_val+1 > 2: tempry = (int)((end_val-strt_val+1)/3) # If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the # arguments to the function itself (Recursive Logic). Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry)) # Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the # function itself (Recursive Logic). Stooge_Sorting(gvn_lst, strt_val+tempry, (end_val)) # Pass the (gvn_lst, strt_val, (end_val-tempry)) as the # arguments to the function itself (Recursive Logic). Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry)) # Give the list as static input and store it in a variable. gvn_lst = [80, 90, 20, -10, 36] # Calculate the length of the given list using the len() function and store # it in another variable. lst_len = len(gvn_lst) # Take a variable and initialize it with the start value as 0. strt_val = 0 # Take another variable and initialize it with the end value as length of the # list-1. end_val = lst_len-1 # Pass the given list, start value, and end value as the arguments to the # Stooge_Sorting() function. Stooge_Sorting(gvn_lst, strt_val, end_val) # Print the given list after sorting. print("The given list after sorting = ", gvn_lst)

**Output:**

The given list after sorting = [-10, 20, 36, 80, 90]

### Method #2: Using Recursion (User Input)

**Approach:**

- Give the list as user input using list(),map(),input(),and split() functions.
- Store it in a variable.
- Calculate the length of the given list using the len() function and store it in another variable.
- Take a variable and initialize it with the start value as 0.
- Take another variable and initialize it with the end value as the length of the list-1.
- Create a Recursive function say Stooge_Sorting() which accepts the given list, start value and end value as the arguments and returns the sorted list.
- Inside the function, check whether the list has any elements using the if conditional statement.
- If it is true then return.
- Check whether the element present at the start value of the list is greater than the element present at the end value using the if conditional statement.
- If it is true, then swap both of them.
- Check whether there are more than two elements using the if conditional statement.
- If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
- Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the function itself (Recursive Logic).
- Pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
- Pass the given list, start value, and end value as the arguments to the Stooge_Sorting() function.
- Print the given list after sorting.
- The Exit of the Program.

**Below is the implementation:**

# Create a Recursive function say Stooge_Sorting() which accepts the given list, # start value and end value as the arguments and returns the sorted list. def Stooge_Sorting(gvn_lst, strt_val, end_val): # Inside the function, check whether the list has any elements using the if # conditional statement. if strt_val >= end_val: # If it is true then return. return # Check whether the element present at the start value of the list is greater # than the element present at the end value using the if conditional statement. if gvn_lst[strt_val] > gvn_lst[end_val]: # If it is true, then swap both of them. gvn_lst[strt_val], gvn_lst[end_val] = gvn_lst[end_val], gvn_lst[strt_val] # Check whether there are more than two elements using the if conditional # statement. if end_val-strt_val+1 > 2: tempry = (int)((end_val-strt_val+1)/3) # If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the # arguments to the function itself (Recursive Logic). Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry)) # Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the # function itself (Recursive Logic). Stooge_Sorting(gvn_lst, strt_val+tempry, (end_val)) # Pass the (gvn_lst, strt_val, (end_val-tempry)) as the # arguments to the function itself (Recursive Logic). Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry)) # Give the list as user input using list(),map(),input(),and split() functions. # Store it in a variable. gvn_lst = list(map(int, input( 'Enter some random List Elements separated by spaces = ').split())) # Calculate the length of the given list using the len() function and store # it in another variable. lst_len = len(gvn_lst) # Take a variable and initialize it with the start value as 0. strt_val = 0 # Take another variable and initialize it with the end value as length of the # list-1. end_val = lst_len-1 # Pass the given list, start value, and end value as the arguments to the # Stooge_Sorting() function. Stooge_Sorting(gvn_lst, strt_val, end_val) # Print the given list after sorting. print("The given list after sorting = ", gvn_lst)

**Output:**

Enter some random List Elements separated by spaces = 56 43 -3 100 13 The given list after sorting = [-3, 13, 43, 56, 100]