Stooge Sort is a recursive sorting algorithm, known for its terrible time complexity. It is based on comparisons.
The algorithm first checks the first element of the data structure and the last, swapping them if they are in the wrong order. If there are more than 3 elements, it calls itself recursively on the initial 2/3 of the list, on the final 2/3 of the list and again on the initial 2/3 of the list, until all the list is sorted.
Its complexity is almost cubic, making it worse than Selection Sort or Insertion Sort.
Average Complexity |
O(n^{log 3 / log 1.5}) O(n^{2.7095...}) |
---|---|
Best Case |
O(n^{log 3 / log 1.5}) O(n^{2.7095...}) |
Worst Case |
O(n^{log 3 / log 1.5}) O(n^{2.7095...}) |
Space Complexity | O(n) |