1792:
235:
120:
271:
160:
1242:
1833:
29:
1202:
1331:
1283:
1857:
1354:
1662:
126:
59:
1695:
1826:
1273:
1852:
1369:
1667:
273:
The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than
184:
69:
1819:
1575:
1455:
1409:
1736:
1324:
314:, e.g. rounding 2/3 of 5 should give 4 rather than 3, as otherwise the sort can fail on certain data.
240:
1715:
1580:
1435:
1261:
52:
1731:
1470:
1621:
1596:
1570:
1374:
1440:
1379:
1340:
1279:
282:
174:
42:
310:
It is important to get the integer sort size used in the recursive calls by rounding the 2/3
1799:
1682:
1549:
1317:
1257:
129:
1743:
1626:
1498:
1399:
1394:
1384:
178:
136:
62:
1304:
1404:
28:
1803:
1748:
1657:
1524:
1493:
1478:
1359:
1269:
277:, a canonical example of a fairly inefficient sort. It is however more efficient than
1846:
1616:
1389:
1234:
1631:
1544:
1414:
1299:
1606:
1430:
1364:
274:
1710:
1690:
1672:
1636:
1565:
1503:
1488:
1450:
1265:
1705:
1641:
1611:
1601:
1539:
1534:
1529:
1508:
1460:
1445:
171:
1791:
1774:
1769:
1483:
292:
If the value at the start is larger than the value at the end, swap them.
278:
1700:
1309:
1313:
401:// If the leftmost element is larger than the rightmost element
1278:(2nd ed.). MIT Press and McGraw-Hill. pp. 161–162.
1807:
295:
If there are three or more elements in the list, then:
243:
187:
139:
72:
1757:
1724:
1681:
1650:
1589:
1558:
1517:
1469:
1423:
1347:
125:
58:
48:
38:
265:
229:
154:
114:
458:// If there are at least 3 elements in the array
33:Visualization of Stooge sort (only shows swaps).
1243:National Institute of Standards and Technology
1827:
1325:
304:Stooge sort the initial 2/3 of the list again
8:
1239:Dictionary of Algorithms and Data Structures
21:
1305:Stooge sort – implementation and comparison
1834:
1820:
1332:
1318:
1310:
1300:Sorting Algorithms (including Stooge sort)
177:. It is notable for its exceptionally bad
254:
242:
208:
198:
186:
138:
93:
83:
71:
596:// Sort the first 2/3 of the array again
1194:
298:Stooge sort the initial 2/3 of the list
16:Inefficient recursive sorting algorithm
230:{\displaystyle O(n^{\log 3/\log 1.5})}
115:{\displaystyle O(n^{\log 3/\log 1.5})}
20:
301:Stooge sort the final 2/3 of the list
288:The algorithm is defined as follows:
7:
1788:
1786:
617:-- Not the best but equal to above
530:// Sort the first 2/3 of the array
14:
563:// Sort the last 2/3 of the array
1790:
266:{\displaystyle O(n^{2.7095...})}
27:
1355:Computational complexity theory
260:
247:
224:
191:
149:
143:
109:
76:
1:
1806:. You can help Knowledge by
1874:
1785:
1663:Batcher odd–even mergesort
1275:Introduction to Algorithms
1210:courses.cs.washington.edu
26:
1668:Pairwise sorting network
1272:(2001) . "Problem 7-3".
614:
326:
1696:Kirkpatrick–Reisch sort
914:src''''
770:src''''
1858:Computer science stubs
1576:Oscillating merge sort
1456:Proportion extend sort
1410:Transdichotomous model
281:. The name comes from
267:
231:
156:
116:
1737:Pre-topological order
1262:Leiserson, Charles E.
268:
232:
157:
117:
1716:Merge-insertion sort
1581:Polyphase merge sort
1436:Cocktail shaker sort
241:
185:
155:{\displaystyle O(n)}
137:
70:
1732:Topological sorting
1494:Cartesian tree sort
23:
1622:Interpolation sort
1597:American flag sort
1590:Distribution sorts
1571:Cascade merge sort
1341:Sorting algorithms
923:src'''
884:src'''
806:-- need every call
263:
227:
152:
112:
1815:
1814:
1783:
1782:
1758:Impractical sorts
1266:Rivest, Ronald L.
1258:Cormen, Thomas H.
422:// Then swap them
283:The Three Stooges
175:sorting algorithm
165:
164:
43:Sorting algorithm
1865:
1853:Comparison sorts
1836:
1829:
1822:
1800:computer science
1794:
1787:
1691:Block merge sort
1651:Concurrent sorts
1550:Patience sorting
1334:
1327:
1320:
1311:
1289:
1253:
1251:
1249:
1221:
1220:
1218:
1216:
1207:
1199:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
272:
270:
269:
264:
259:
258:
236:
234:
233:
228:
223:
222:
212:
161:
159:
158:
153:
130:space complexity
121:
119:
118:
113:
108:
107:
97:
31:
24:
1873:
1872:
1868:
1867:
1866:
1864:
1863:
1862:
1843:
1842:
1841:
1840:
1784:
1779:
1753:
1744:Pancake sorting
1720:
1677:
1646:
1627:Pigeonhole sort
1585:
1554:
1518:Insertion sorts
1513:
1499:Tournament sort
1471:Selection sorts
1465:
1419:
1400:Integer sorting
1395:Sorting network
1385:Comparison sort
1343:
1338:
1296:
1286:
1270:Stein, Clifford
1256:
1247:
1245:
1233:Black, Paul E.
1232:
1229:
1224:
1214:
1212:
1205:
1201:
1200:
1196:
1192:
1187:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
920:innerStoogesort
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
890:innerStoogesort
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
860:innerStoogesort
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
725:innerStoogesort
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
689:innerStoogesort
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
659:innerStoogesort
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
608:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
320:
250:
239:
238:
194:
183:
182:
179:time complexity
135:
134:
79:
68:
67:
34:
17:
12:
11:
5:
1871:
1869:
1861:
1860:
1855:
1845:
1844:
1839:
1838:
1831:
1824:
1816:
1813:
1812:
1795:
1781:
1780:
1778:
1777:
1772:
1767:
1761:
1759:
1755:
1754:
1752:
1751:
1749:Spaghetti sort
1746:
1741:
1740:
1739:
1728:
1726:
1722:
1721:
1719:
1718:
1713:
1708:
1703:
1698:
1693:
1687:
1685:
1679:
1678:
1676:
1675:
1670:
1665:
1660:
1658:Bitonic sorter
1654:
1652:
1648:
1647:
1645:
1644:
1639:
1634:
1629:
1624:
1619:
1614:
1609:
1604:
1599:
1593:
1591:
1587:
1586:
1584:
1583:
1578:
1573:
1568:
1562:
1560:
1556:
1555:
1553:
1552:
1547:
1542:
1537:
1532:
1527:
1525:Insertion sort
1521:
1519:
1515:
1514:
1512:
1511:
1509:Weak-heap sort
1506:
1501:
1496:
1491:
1486:
1481:
1479:Selection sort
1475:
1473:
1467:
1466:
1464:
1463:
1458:
1453:
1448:
1443:
1438:
1433:
1427:
1425:
1424:Exchange sorts
1421:
1420:
1418:
1417:
1412:
1407:
1402:
1397:
1392:
1387:
1382:
1377:
1372:
1367:
1362:
1360:Big O notation
1357:
1351:
1349:
1345:
1344:
1339:
1337:
1336:
1329:
1322:
1314:
1308:
1307:
1302:
1295:
1294:External links
1292:
1291:
1290:
1284:
1254:
1228:
1225:
1223:
1222:
1193:
1191:
1188:
615:
612:
609:
327:
324:
321:
319:
318:Implementation
316:
308:
307:
306:
305:
302:
299:
293:
262:
257:
253:
249:
246:
226:
221:
218:
215:
211:
207:
204:
201:
197:
193:
190:
163:
162:
151:
148:
145:
142:
132:
123:
122:
111:
106:
103:
100:
96:
92:
89:
86:
82:
78:
75:
65:
56:
55:
50:
49:Data structure
46:
45:
40:
36:
35:
32:
15:
13:
10:
9:
6:
4:
3:
2:
1870:
1859:
1856:
1854:
1851:
1850:
1848:
1837:
1832:
1830:
1825:
1823:
1818:
1817:
1811:
1809:
1805:
1802:article is a
1801:
1796:
1793:
1789:
1776:
1773:
1771:
1768:
1766:
1763:
1762:
1760:
1756:
1750:
1747:
1745:
1742:
1738:
1735:
1734:
1733:
1730:
1729:
1727:
1723:
1717:
1714:
1712:
1709:
1707:
1704:
1702:
1699:
1697:
1694:
1692:
1689:
1688:
1686:
1684:
1680:
1674:
1671:
1669:
1666:
1664:
1661:
1659:
1656:
1655:
1653:
1649:
1643:
1640:
1638:
1635:
1633:
1630:
1628:
1625:
1623:
1620:
1618:
1617:Counting sort
1615:
1613:
1610:
1608:
1605:
1603:
1600:
1598:
1595:
1594:
1592:
1588:
1582:
1579:
1577:
1574:
1572:
1569:
1567:
1564:
1563:
1561:
1557:
1551:
1548:
1546:
1543:
1541:
1538:
1536:
1533:
1531:
1528:
1526:
1523:
1522:
1520:
1516:
1510:
1507:
1505:
1502:
1500:
1497:
1495:
1492:
1490:
1487:
1485:
1482:
1480:
1477:
1476:
1474:
1472:
1468:
1462:
1459:
1457:
1454:
1452:
1449:
1447:
1444:
1442:
1441:Odd–even sort
1439:
1437:
1434:
1432:
1429:
1428:
1426:
1422:
1416:
1413:
1411:
1408:
1406:
1405:X + Y sorting
1403:
1401:
1398:
1396:
1393:
1391:
1390:Adaptive sort
1388:
1386:
1383:
1381:
1378:
1376:
1373:
1371:
1368:
1366:
1363:
1361:
1358:
1356:
1353:
1352:
1350:
1346:
1342:
1335:
1330:
1328:
1323:
1321:
1316:
1315:
1312:
1306:
1303:
1301:
1298:
1297:
1293:
1287:
1285:0-262-03293-7
1281:
1277:
1276:
1271:
1267:
1263:
1259:
1255:
1244:
1240:
1236:
1235:"stooge sort"
1231:
1230:
1226:
1211:
1204:
1198:
1195:
1189:
893:src''
854:src''
610:
322:
317:
315:
313:
303:
300:
297:
296:
294:
291:
290:
289:
286:
284:
280:
276:
255:
251:
244:
219:
216:
213:
209:
205:
202:
199:
195:
188:
180:
176:
173:
169:
146:
140:
133:
131:
128:
124:
104:
101:
98:
94:
90:
87:
84:
80:
73:
66:
64:
61:
57:
54:
51:
47:
44:
41:
37:
30:
25:
19:
1808:expanding it
1797:
1764:
1683:Hybrid sorts
1632:Proxmap sort
1545:Library sort
1415:Quantum sort
1274:
1246:. Retrieved
1238:
1215:14 September
1213:. Retrieved
1209:
1197:
821:fromIntegral
311:
309:
287:
167:
166:
18:
1765:Stooge sort
1607:Bucket sort
1559:Merge sorts
1431:Bubble sort
1375:Inplacement
1365:Total order
275:bubble sort
168:Stooge sort
63:performance
22:Stooge sort
1847:Categories
1711:Spreadsort
1673:Samplesort
1637:Radix sort
1566:Merge sort
1504:Cycle sort
1489:Smoothsort
1451:Gnome sort
1190:References
650:stoogesort
644:stoogesort
620:stoogesort
566:stoogesort
533:stoogesort
500:stoogesort
332:stoogesort
323:Pseudocode
127:Worst-case
60:Worst-case
1706:Introsort
1642:Flashsort
1612:Burstsort
1602:Bead sort
1540:Tree sort
1535:Splaysort
1530:Shellsort
1461:Quicksort
1446:Comb sort
1380:Stability
1203:"CSE 373"
1163:replaceAt
1151:otherwise
1100:replaceAt
1079:replaceAt
1037:otherwise
1013:replaceAt
1007:replaceAt
776:otherwise
256:2.7095...
217:
203:
172:recursive
102:
88:
1775:Bogosort
1770:Slowsort
1484:Heapsort
863:src'
788:src'
782:src'
329:function
279:Slowsort
1701:Timsort
1248:18 June
1227:Sources
611:Haskell
312:upwards
1348:Theory
1282:
671:length
599:return
365:length
1798:This
1725:Other
1370:Lists
1206:(PDF)
1184:value
1172:index
1139:value
1127:index
1121:value
1118:index
1097:->
1091:->
1085:->
1046:where
977:->
971:->
965:->
962:=>
815:floor
785:where
722:->
716:->
710:->
707:=>
641:->
638:=>
467:floor
338:array
170:is a
53:Array
39:Class
1804:stub
1280:ISBN
1250:2011
1217:2020
998:>
980:swap
944:swap
794:swap
761:>
455:then
449:>
404:swap
398:then
392:>
1088:Int
1070:src
1055:src
1043:src
1016:src
983:src
974:Int
968:Int
953:Ord
848:3.0
797:src
728:src
719:Int
713:Int
698:Ord
674:src
662:src
653:src
629:Ord
220:1.5
214:log
200:log
181:of
105:1.5
99:log
85:log
1849::
1268:;
1264:;
1260:;
1241:.
1237:.
1208:.
1166:xs
1145:xs
1130:==
1112:xs
1082:::
1073:!!
1058:!!
947:::
692:::
668:((
623:::
470:((
425:if
386:if
383:){
285:.
237:=
1835:e
1828:t
1821:v
1810:.
1333:e
1326:t
1319:v
1288:.
1252:.
1219:.
1181:)
1178:1
1175:-
1169:(
1160::
1157:x
1154:=
1148:|
1142::
1136:=
1133:0
1124:|
1115:)
1109::
1106:x
1103:(
1094:a
1076:j
1067:=
1064:b
1061:i
1052:=
1049:a
1040:=
1034:|
1031:b
1028:i
1025:)
1022:a
1019:j
1010:(
1004:=
1001:b
995:a
992:|
989:j
986:i
959:)
956:a
950:(
941:)
938:t
935:-
932:j
929:(
926:i
917:=
911:j
908:)
905:t
902:+
899:i
896:(
887:=
881:)
878:t
875:-
872:j
869:(
866:i
857:=
851:)
845:/
842:)
839:1
836:+
833:i
830:-
827:j
824:(
818:(
812:=
809:t
803:j
800:i
791:=
779:=
773:|
767:=
764:2
758:)
755:1
752:+
749:i
746:-
743:j
740:(
737:|
734:j
731:i
704:)
701:a
695:(
686:)
683:1
680:-
677:)
665:0
656:=
647:=
635:)
632:a
626:(
605:}
602:L
593:)
590:t
587:-
584:j
581:,
578:i
575:,
572:L
569:(
560:)
557:j
554:,
551:t
548:+
545:i
542:,
539:L
536:(
527:)
524:t
521:-
518:j
515:,
512:i
509:,
506:L
503:(
497:)
494:3
491:/
488:)
485:1
482:+
479:i
476:-
473:j
464:=
461:t
452:2
446:)
443:1
440:+
437:i
434:-
431:j
428:(
419:)
416:L
413:,
410:L
407:(
395:L
389:L
380:1
377:-
374:)
371:L
368:(
362:=
359:j
356:,
353:0
350:=
347:i
344:,
341:L
335:(
261:)
252:n
248:(
245:O
225:)
210:/
206:3
196:n
192:(
189:O
150:)
147:n
144:(
141:O
110:)
95:/
91:3
81:n
77:(
74:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
