Stooge Sort

The Stooge sort is a recursive sorting algorithm. It is defined as below (for ascending order sorting).

Step 1 : If value at index 0 is greater than value at last index,                
         swap them. 
Step 2: Recursively, 
        a) Stooge sort the initial 2/3rd of the array. 
        b) Stooge sort the last 2/3rd of the array. 
        c) Stooge sort the initial 2/3rd again to confirm.

NOTE: Always take the ceil of ((2/3)*N) for selecting elements.

Illustration

Input :   2 4 5 3 1
Output : 1 2 3 4 5
Explanation:
Initially, swap 2 and 1 following above step 1.
          1 4 5 3 2
          Now, recursively sort initial 2/3rd of the elements.
          1 4 5 3 2
          1 3 4 5 2 
          Then, recursively sort last 2/3rd of the elements.
          1 3 4 5 2
          1 2 3 4 5
          Again, sort the initial 2/3rd of the elements to                              
          confirm final data is sorted.
          1 2 3 4 5

CODE

# Python program to implement stooge sort 
  
def stoogesort(arr, l, h): 
    if l >= h: 
        return
   
    # If first element is smaller 
    # than last, swap them 
    if arr[l]>arr[h]: 
        t = arr[l] 
        arr[l] = arr[h] 
        arr[h] = t 
   
    # If there are more than 2 elements in 
    # the array 
    if h-l + 1 > 2: 
        t = (int)((h-l + 1)/3) 
   
        # Recursively sort first 2 / 3 elements 
        stoogesort(arr, l, (h-t)) 
   
        # Recursively sort last 2 / 3 elements 
        stoogesort(arr, l + t, (h)) 
   
        # Recursively sort first 2 / 3 elements 
        # again to confirm 
        stoogesort(arr, l, (h-t)) 
   
  
# driver  
arr = [2, 4, 5, 3, 1] 
n = len(arr) 
  
stoogesort(arr, 0, n-1) 
   
for i in range(0, n): 
    print(arr[i], end = ' ') 

Output:            1 2 3 4 5

Time complexity

Worst complexity: n^(log3/log1.5)
Average complexity: n^(log3/log1.5)
Best complexity: n^(log3/log1.5)
Space complexity: n
Stable: No
Class: Comparison sort
Worst-case space complexity: O(n)

T(n) = 3T(3n/2) + ?(1)
Solution of above recurrence is O(n^{(log3/log1.5)}) = O(n^2.709), hence it is slower than even bubble sort(n^2).