I suspected that a hybrid of a stooge and a bogosort would be quicker than a straight bogosort. Turns out I was right.
Hybrid Stooge-Bogo sort
- Bogosort the first 2/3 of the list
- Bogosort the last 2/3 of the list
- Bogosort the first 2/3 of the list
Turns out though, that the bogosort is quicker in cases where the list is already sorted since it does fewer “is it sorted” checks before exiting.
A straight stooge sort is usually quicker than the stooge-bogo hybrid though.
There. Isn’t that useful information?
Pitting Stooge Sort, Bogo Sort and Hybrid bogo-stooge sorting against each other:
For length 1 Bogo wins.(stooge : 0.000003, Hybrid: 0.000062 Bogo: 0.000002)
For length 2 Stooge wins.(stooge : 0.000003, Hybrid: 0.000020 Bogo: 0.000467)
For length 3 Stooge wins.(stooge : 0.000028, Hybrid: 0.000177 Bogo: 0.000169)
For length 4 Stooge wins.(stooge : 0.000074, Hybrid: 0.001401 Bogo: 0.004980)
For length 5 Stooge wins.(stooge : 0.000110, Hybrid: 0.005993 Bogo: 0.013229)
For length 6 Stooge wins.(stooge : 0.000151, Hybrid: 0.002046 Bogo: 0.039309)
For length 7 Stooge wins.(stooge : 0.000272, Hybrid: 0.038909 Bogo: 0.125351)
For length 8 Stooge wins.(stooge : 0.000253, Hybrid: 0.095385 Bogo: 0.777875)
For length 9 Stooge wins.(stooge : 0.000410, Hybrid: 0.246479 Bogo: 19.195493)
To be interesting and add Bozosort to the list instead of Stooge sort:
For length 1 Bogo wins.(bozo : 0.000004, Hybrid: 0.000017 Bogo: 0.000002)
For length 2 Bogo wins.(bozo : 0.000020, Hybrid: 0.000020 Bogo: 0.000002)
For length 3 Bogo wins.(bozo : 0.000034, Hybrid: 0.001125 Bogo: 0.000031)
For length 4 Bozo wins.(bozo : 0.000117, Hybrid: 0.001645 Bogo: 0.004542)
For length 5 Bozo wins.(bozo : 0.000231, Hybrid: 0.010748 Bogo: 0.009622)
For length 6 Bozo wins.(bozo : 0.004700, Hybrid: 0.006521 Bogo: 0.022846)
For length 7 Hybrid wins. (bozo : 0.072314, Hybrid: 0.038041 Bogo: 0.144553)
For length 8 Hybrid wins. (bozo : 0.242777, Hybrid: 0.108764 Bogo: 23.163011)
For length 9 Hybrid wins. (bozo : 3.688617, Hybrid: 0.221937 Bogo: 2.503227)
This wasn’t strictly a fair test, since each of the times listed for a given length is actually a different list, but it should give some idea. Testing after each swap (bozosort) seems to beat testing after many swaps (bogosort) in some cases.