Stooge Sort

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.