Two implementations are provided:
- Pseudo code,
- A basic implementation, and
- A array-based implementation.
When compiled with the -O2 option, the basic implementation
sorts an array of size ten thousand in 113 seconds while the enhanced
array-based implementation sorts it in 3 seconds.
Pseudo Code
To stooge sort a list:
If the first and last entries are out of order swap them.
If the list has more than 2 entries;
Stooge sort the first 2/3rds,
Stooge sort the second 2/3rds, and
Stooge sort the first 2/3rds again.
end
end
Basic Implementation
A straight-forward implementation of the pseudo code.
Array-based Implementation
If no change was made to the second third, do not call stooge sort again on
the first third.
Observation
Every implementation of stooge sort found on the Internet by this author
determines 'thirds' by
calculating n/3 where n is the number of items to be sorted. Note
that this causes stooge sort to be very inefficient as an array with 5 entries
is stooge sorted with arrays of size 4, not 3. Using (n + 1)/3 reduces
the run-time by a factor of three.