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.
Java
// Java program to implement stooge sort import java.io.*; Â
public class stooge {  // Function to implement stooge sort  static void stoogesort(int arr[], int l, int h)  {   if (l >= h)   return; Â
  // If first element is smaller   // than last,swap them   if (arr[l] > arr[h])   {    int 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)   {    int t = (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 Code  public static void main(String args[])  {   int arr[] = {2, 4, 5, 3, 1};   int n = arr.length; Â
  stoogesort(arr, 0, n-1); Â
  for (int i=0; i < n; i++)    System.out.print(arr[i] + " ");  } } // Code Contributed by Mohit Gupta_OMG <(0_o)> |
Output:
1 2 3 4 5
Time Complexity:
The running time complexity of stooge sort can be written as,
T(n) = 3T(3n/2) + O(1)
Solution of above recurrence is O(n(log3/log1.5)) = O(n2.709), hence it is slower than even bubble sort(n2).
Auxiliary Space: O(n)
Please refer complete article on Stooge Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Read More here to that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Read More Information here to that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Find More Info here on that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Read More Info here on that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]
… [Trackback]
[…] Here you can find 86543 more Information to that Topic: geeksforgeeks.org/java-program-for-stooge-sort/ […]