digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Business

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

Stooge sort
Sorting stoogesort anim.gif
Visualization of Stooge sort.
Class Sorting algorithm
Data structure Array
Worst case performance O(nlog 3 /log 1.5)
Worst case space complexity O(n)

Stooge sort is a recursive sorting algorithm with a time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...). The running time of the algorithm is thus extremely slow compared to efficient sorting algorithms, such as Merge sort, and is even slower than Bubble sort, a canonical example of a fairly inefficient and simple sort.

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 three or more elements in the current list subset, then:
    • Stooge sort the initial 2/3 of the list
    • Stooge sort the final 2/3 of the list
    • Stooge sort the initial 2/3 of the list again
  • else: exit the procedure

The algorithm gets its name from slapstick routines of the Three Stooges, in which each stooge hits the other two.[citation needed]

Implementation[edit]

 function stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if (j - i + 1) >= 3 then
         t = (j - i + 1) / 3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

References[edit]

External links[edit]



Original courtesy of Wikipedia: http://en.wikipedia.org/wiki/Stooge_sort — Please support Wikipedia.
A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia.
854 videos foundNext > 

Stooge Sort

Visualization and "audibilization" of the Stooge Sort algorithm. Sorts a random shuffle of the integers [1,64] using Stooge sort. It uses the implementation ...

Stooge sort (30)

http://nayuki.eigenstate.org/page/sorting-algorithms-demo-java.

Tim Sort

Visualization and "audibilization" of the TimSort algorithm. Sorts a random shuffle of the integers [1100] using TimSort (standard sorting algorithm in Pyth...

Stooge

фан-видео к роману.

Slow Sort

Visualization and "audibilization" of the Slow Sort algorithm. Sorts a random shuffle of the integers [1,50] using slow sort. It uses the implementation from...

Stupid sort (30)

http://nayuki.eigenstate.org/page/sorting-algorithms-demo-java.

Stooge

Stooge.

I Got Nothing - Iggy and the Stooge

Live from the Metallic KO album. The best live album for my money, as you can literally hear the beers being thrown at the band. Also, gotta love James Willi...

Block Merge Sort (WikiSort)

Visualization and "audibilization" of "Block Merge Sort" algorithm. Sorts a random shuffle of the integers [1100] using Block Merge Sort, which is an in-pla...

Cycle Sort

Visualization and "audibilization" of "Cycle Sort" algorithm. Sorts a random shuffle of the integers [1100] using Cycle Sort - http://en.wikipedia.org/wiki/...

854 videos foundNext > 

We're sorry, but there's no news about "Stooge sort" right now.

Loading

Oops, we seem to be having trouble contacting Twitter

Talk About Stooge sort

You can talk about Stooge sort with people all over the world in our discussions.

Support Wikipedia

A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia. Please add your support for Wikipedia!