Stooge sort is a recursive sorting algorithm with a time complexity of about O(n^2.7). The exponent's exact value is log(3)/log(1.5).

The algorithm is defined as follows:

• If the value at the end is smaller than the value at the start, swap them.
• If there are 2 or more elements in the current list subset, then: (or else, exit procedure)
• Sort the initial 2/3 of the list
• Sort the final 2/3 of the list
• Sort the initial 2/3 of the list again

Implementations

This sort implemented in Java:

// Interfacing method (to invoke the internal method with the correct initial values)
void stoogeSort(int[] a){
 stoogeSort(a,0,a.length);
}

// Internal method
void stoogeSort(int[] a,int s,int e){
 if(a[e-1]<a[s]){
  int temp=a[s];
  a[s]=a[e-1];
  a[e-1]=temp;
 }
 int len=e-s;
 if(len>1){
  int third=len/3; // Reminder: This is (truncated) integer division
  stoogeSort(a,s,e-third);
  stoogeSort(a,s+third,e);
  stoogeSort(a,s,e-third);
 }
}

External links

Everything2.com - Stooge sort