Combsort vs Quicksort

Combsort on short arrays is 20-30% faster than quicksort!
using combsort from:
https://www.reddit.com/r/frozenvoid/wiki/void2/sort_h

I rather use sleepsort.

Markov sort is more flexible https://github.com/saniv/markov_sort

>>3
Were you released from jail?

Lasersort v0.1a

Array-sweep [1 to n] min,max, mark every elem higher or lower than current peaks

Array-sweep [n to 1] putting min marks at start of new array, max at end working inward, continue running phase 1

>>3
How well does it perform against OP's?

Here is the data for combsort on arrays of 64bit ints from 4elems to 99999elems
E=Elements, P=Per element cycles A=Total cycles:
E:4: P:240.000000: A:960
E:6: P:122.000000: A:732
E:9: P:160.000000: A:1440
E:13: P:201.230769: A:2616
E:19: P:181.263158: A:3444
E:28: P:186.000000: A:5208
E:42: P:196.571429: A:8256
E:63: P:210.285714: A:13248
E:94: P:204.893617: A:19260
E:141: P:218.382979: A:30792
E:211: P:229.421801: A:48408
E:316: P:227.620253: A:71928
E:474: P:243.848101: A:115584
E:711: P:245.907173: A:174840
E:1066: P:257.707317: A:274716
E:1599: P:275.947467: A:441240
E:2398: P:273.527940: A:655920
E:3597: P:299.012510: A:1075548
E:5395: P:298.338462: A:1609536
E:8092: P:308.943648: A:2499972
E:12138: P:327.832921: A:3979236
E:18207: P:389.067556: A:7083753
E:27310: P:440.737459: A:12036540
E:40965: P:305.371927: A:12509561
E:61447: P:283.676372: A:17431062
E:92170: P:284.794065: A:26249469

Here is the same data for stack-free quicksort from http://alienryderflex.com/quicksort/
modified to work on 64bit signed ints:

E:4: P:2454.750000: A:9819
E:6: P:130.500000: A:783
E:9: P:127.777778: A:1150
E:13: P:145.538462: A:1892
E:19: P:155.315789: A:2951
E:28: P:157.821429: A:4419
E:42: P:167.238095: A:7024
E:63: P:168.285714: A:10602
E:94: P:180.446809: A:16962
E:141: P:190.737589: A:26894
E:211: P:194.905213: A:41125
E:316: P:201.892405: A:63798
E:474: P:214.772152: A:101802
E:711: P:218.734177: A:155520
E:1066: P:229.629456: A:244785
E:1599: P:247.624140: A:395951
E:2398: P:262.662636: A:629865
E:3597: P:270.446761: A:972797
E:5395: P:275.748285: A:1487662
E:8092: P:293.014459: A:2371073
E:12138: P:296.361262: A:3597233
E:18207: P:311.284561: A:5667558
E:27310: P:319.469132: A:8724702
E:40965: P:320.126986: A:13114002
E:61447: P:326.403535: A:20056518
E:92170: P:320.429098: A:29533950

Radix sort results:

E:4: P:9018.750000: A:36075
E:6: P:3752.500000: A:22515
E:9: P:2296.666667: A:20670
E:13: P:1621.153846: A:21075
E:19: P:1455.000000: A:27645
E:28: P:836.250000: A:23415
E:42: P:624.285714: A:26220
E:63: P:547.380952: A:34485
E:94: P:426.382979: A:40080
E:141: P:351.702128: A:49590
E:211: P:308.317536: A:65055
E:316: P:297.958861: A:94155
E:474: P:225.189873: A:106740
E:711: P:209.620253: A:149040
E:1066: P:199.601313: A:212775
E:1599: P:177.729831: A:284190
E:2398: P:214.366138: A:514050
E:3597: P:232.885738: A:837690
E:5395: P:237.241891: A:1279920
E:8092: P:239.228868: A:1935840
E:12138: P:244.903609: A:2972640
E:18207: P:284.405998: A:5178180
E:27310: P:313.902819: A:8572686
E:40965: P:286.470572: A:11735267
E:61447: P:264.355266: A:16243838
E:92170: P:245.278594: A:22607328

And just for fun here are result from bubblesort:
E:4: P:90.000000: A:360
E:6: P:161.666667: A:970
E:9: P:130.000000: A:1170
E:13: P:246.923077: A:3210
E:19: P:265.789474: A:5050
E:28: P:402.500000: A:11270
E:42: P:531.904762: A:22340
E:63: P:614.285714: A:38700
E:94: P:995.744681: A:93600
E:141: P:1263.120567: A:178100
E:211: P:1630.616114: A:344060
E:316: P:2383.512658: A:753190
E:474: P:3361.645570: A:1593420
E:711: P:4465.864979: A:3175230
E:1066: P:6433.968105: A:6858610
E:1599: P:7135.928705: A:11410350
E:2398: P:10747.141368: A:25771645
E:3597: P:16610.630525: A:59748438
E:5395: P:25080.200741: A:135307683
E:8092: P:32229.155957: A:260798330
E:12138: P:48650.944142: A:590525160
E:18207: P:82714.265942: A:1505978640
E:27310: P:126527.776053: A:3455473564
E:40965: P:194933.108458: A:7985434788
E:61447: P:294654.517910: A:18105636162
E:92170: P:443030.943018: A:40834162018

>>5
685 passes over E:1000, 346203 live iter for a trial of the one-sided version

3317 passes on E:5000, 8286093 live iter, 0.27 sec

346000 / 1000 || 1000 / 3 (340 | 330)
8286000 / 5000 || 5000 / 3 (1657 | 1666)

correctly placing about 3 values per pass ?

lol that can't be right, 1.5 values

Low+High gets ~1700 passes on E:5000, live or active iter is a pretty flat 50% of 1700x5000, 0.2 sec



function lasersort(inp) #0.2
n = size(inp, 1);
lowbol = falses(n);
highbol = falses(n); #
skipbol = falses(n);
indperm = zeros(Int32, n);
lowval = inp[1];
highval = inp[1]; #
# tempval = 0;
starti = 1;
endi = n;
xtrick = false;
ztrickl = false;
ztrickh = false; #
freshval = true;
runvec = collect(1:n);
val = 0;
maxint = 0;
liveiter = 0;

for(iter = 1:n)
val = inp[iter];
lowbol[iter] = val<=lowval;
lowval = lowval<val? lowval:val;
## print(val, ", l:", lowbol[iter],", L:", lowval, "\n");
highbol[iter] = val>=highval; #
highval = highval>val? highval:val; #
end;

while(starti<=endi)
maxint +=1;
if(maxint > 20000) break; end;
runvec = runvec[end:-1:1];
freshval = true;

for(iter = runvec)
if(skipbol[iter])
continue;
end;
val = inp[iter];

if(freshval)
lowval = inp[iter];
highval = inp[iter]; #
freshval = lowbol[iter] | highbol[iter];
end;
xtrick = lowbol[iter] | highbol[iter];
ztrickl = lowbol[iter];
ztrickh = highbol[iter]; #
lowbol[iter] = val <= lowval;
highbol[iter] = val >= highval; #

if(!xtrick)
lowval = val<lowval? val:lowval;
highval = val>highval? val:highval; #
end;
if(lowbol[iter] & ztrickl)
indperm[starti] = val;
starti += 1;
skipbol[iter] = true;
end;
if(highbol[iter] & ztrickh) #
indperm[endi] = val; #
endi -= 1; #
skipbol[iter] = true; #
end; #
liveiter += 1;
## print(val, ", l:", lowbol[iter],", L:", lowval, "\n");
end;
end; #while

print("liveval : ", val, "\n", maxint, " - max\n", liveiter, " liveiter \n");
return(indperm);
end;


combsort on big arrays from 4 to 500M elements on 8GB Haswell machine:
E=Elements, P=Per element CPU cycles A=All cycles per array

E:4: P:126.000000: A:504
E:6: P:46.666667: A:280
E:9: P:63.111111: A:568
E:13: P:82.153846: A:1068
E:19: P:73.263158: A:1392
E:28: P:69.857143: A:1956
E:42: P:74.666667: A:3136
E:63: P:80.063492: A:5044
E:94: P:78.723404: A:7400
E:141: P:83.375887: A:11756
E:211: P:87.336493: A:18428
E:316: P:87.291139: A:27584
E:474: P:94.042194: A:44576
E:711: P:94.677918: A:67316
E:1066: P:99.290807: A:105844
E:1599: P:106.158849: A:169748
E:2398: P:112.078399: A:268764
E:3597: P:113.502363: A:408268
E:5395: P:114.721038: A:618920
E:8092: P:118.213544: A:956584
E:12138: P:126.343055: A:1533552
E:18207: P:154.623167: A:2815224
E:27310: P:134.377884: A:3669860
E:40965: P:144.772074: A:5930588
E:61447: P:143.219555: A:8800412
E:92170: P:135.084301: A:12450720
E:138255: P:136.001982: A:18802954
E:207382: P:140.676471: A:29173768
E:311073: P:158.890524: A:49426552
E:466609: P:168.440857: A:78596020
E:699913: P:206.765509: A:144717868
E:1049869: P:220.802439: A:231813636
E:1574803: P:238.170872: A:375072204
E:2362204: P:254.625572: A:601477544
E:3543306: P:260.572507: A:923288128
E:5314959: P:286.153259: A:1520892840
E:7972438: P:302.807983: A:2414117872
E:11958657: P:304.034667: A:3635846304
E:17937985: P:313.029681: A:5615121716
E:26906977: P:319.579795: A:8598926196
E:40360465: P:327.371869: A:13212880844
E:60540697: P:340.823668: A:20633702404
E:90811045: P:347.795310: A:31583655516
E:136216567: P:360.035844: A:49042846684
E:204324850: P:369.553056: A:75508872708
E:306487275: P:379.343941: A:116264090808
E:459730912: P:391.697136: A:180075281480

stack-free quicksort on same machine;

E:4: P:1451.000000: A:5804
E:6: P:76.000000: A:456
E:9: P:68.888889: A:620
E:13: P:79.384615: A:1032
E:19: P:88.000000: A:1672
E:28: P:91.428571: A:2560
E:42: P:93.523810: A:3928
E:63: P:97.841270: A:6164
E:94: P:104.127660: A:9788
E:141: P:107.546099: A:15164
E:211: P:110.104265: A:23232
E:316: P:114.088608: A:36052
E:474: P:118.734177: A:56280
E:711: P:123.167370: A:87572
E:1066: P:129.493433: A:138040
E:1599: P:140.007505: A:223872
E:2398: P:148.366972: A:355784
E:3597: P:149.276619: A:536948
E:5395: P:156.174235: A:842560
E:8092: P:166.404844: A:1346548
E:12138: P:167.287527: A:2030536
E:18207: P:175.575768: A:3196708
E:27310: P:186.828415: A:5102284
E:40965: P:191.612938: A:7849424
E:61447: P:201.520465: A:12382828
E:92170: P:212.107584: A:19549956
E:138255: P:212.130397: A:29328088
E:207382: P:223.200799: A:46287828
E:311073: P:226.462625: A:70446408
E:466609: P:231.781316: A:108151248
E:699913: P:244.811438: A:171346708
E:1049869: P:246.575540: A:258872016
E:1574803: P:251.538586: A:396123720
E:2362204: P:259.766103: A:613620528
E:3543306: P:268.077291: A:949879872
E:5314959: P:277.104510: A:1472799112
E:7972438: P:279.482747: A:2228158876
E:11958657: P:289.235403: A:3458866976
E:17937985: P:295.196890: A:5295237388
E:26906977: P:305.060269: A:8208249636
E:40360465: P:312.259452: A:12602936672
E:60540697: P:324.503729: A:19645681908
E:90811045: P:323.474085: A:29375019648
E:136216567: P:330.482661: A:45017213560
E:204324850: P:340.709381: A:69615393088
E:306487275: P:348.693358: A:106870077006
E:459730912: P:356.788521: A:164026712308

stock qsort from GNU libc. same machine

E:4: P:2923.000000: A:11692
E:6: P:185.333333: A:1112
E:9: P:156.888889: A:1412
E:13: P:174.153846: A:2264
E:19: P:163.157895: A:3100
E:28: P:163.428571: A:4576
E:42: P:166.095238: A:6976
E:63: P:172.571429: A:10872
E:94: P:177.063830: A:16644
E:141: P:302.950355: A:42716
E:211: P:189.933649: A:40076
E:316: P:205.443038: A:64920
E:474: P:207.780591: A:98488
E:711: P:220.106892: A:156496
E:1066: P:248.757974: A:265176
E:1599: P:238.506567: A:381372
E:2398: P:250.503753: A:600708
E:3597: P:262.383097: A:943792
E:5395: P:273.781650: A:1477052
E:8092: P:282.866535: A:2288956
E:12138: P:294.521338: A:3574900
E:18207: P:311.780304: A:5676584
E:27310: P:326.595972: A:8919336
E:40965: P:333.333236: A:13654996
E:61447: P:347.932169: A:21379388
E:92170: P:363.562721: A:33509576
E:138255: P:378.697595: A:52356836
E:207382: P:389.887994: A:80855752
E:311073: P:401.862264: A:125008500
E:466609: P:412.744203: A:192590160
E:699913: P:426.258081: A:298343572
E:1049869: P:438.143715: A:459993504
E:1574803: P:449.694203: A:708179780
E:2362204: P:464.500092: A:1097243976
E:3543306: P:480.107171: A:1701166620
E:5314959: P:490.746251: A:2608296204
E:7972438: P:507.184164: A:4043494304
E:11958657: P:517.374738: A:6187107028
E:17937985: P:532.269010: A:9547833520
E:26906977: P:552.614817: A:14869194180
E:40360465: P:564.514971: A:22784086724
E:60540697: P:580.043322: A:35116226992
E:90811045: P:593.544297: A:53900377884
E:136216567: P:605.975038: A:82543839356
E:204324850: P:625.095113: A:127722465148
E:306487275: P:662.694670: A:203107483632
fail#1 //the below array inexplicably failed to sort correctly(detected by sort checker
E:459730912: P:694.559053: A:319310266800

Combsort on D(LDC2) without Druntime(via BetterC)
E:4: P:118.750000: A:475
E:6: P:91.666667: A:550
E:9: P:110.000000: A:990
E:13: P:94.615385: A:1230
E:19: P:98.947368: A:1880
E:28: P:93.750000: A:2625
E:42: P:91.666667: A:3850
E:63: P:86.111111: A:5425
E:94: P:84.946809: A:7985
E:141: P:91.170213: A:12855
E:211: P:95.308057: A:20110
E:316: P:97.278481: A:30740
E:474: P:104.694093: A:49625
E:711: P:108.066104: A:76835
E:1066: P:115.492495: A:123115
E:1599: P:123.286429: A:197135
E:2398: P:126.959967: A:304450
E:3597: P:136.010564: A:489230
E:5395: P:140.271548: A:756765
E:8092: P:148.577608: A:1202290
E:12138: P:155.506673: A:1887540
E:18207: P:159.985994: A:2912865
E:27310: P:168.229769: A:4594355
E:40965: P:176.056756: A:7212165
E:61447: P:173.712142: A:10674090
E:92170: P:180.933438: A:16676635
E:138255: P:181.149036: A:25044760
E:207382: P:182.660964: A:37880596
E:311073: P:177.659385: A:55265038
E:466609: P:180.435508: A:84192832
E:699913: P:200.283395: A:140180952
E:1049869: P:214.677782: A:225383548
E:1574803: P:232.581012: A:366269276
E:2362204: P:243.583477: A:575393864
E:3543306: P:253.243755: A:897320116
E:5314959: P:266.213236: A:1414912432
E:7972438: P:276.865819: A:2207295576
E:11958657: P:291.195920: A:3482312132
E:17937985: P:299.418881: A:5370971404
E:26906977: P:306.176917: A:8238295256
E:40360465: P:321.251127: A:12965844852
E:60540697: P:334.651006: A:20260005156
E:90811045: P:343.705324: A:31212239628
E:136216567: P:356.228590: A:48524235540
E:204324850: P:365.289523: A:74637727024
E:306487275: P:385.757868: A:118229877692
E:459730912: P:381.731815: A:175493915232

And with runtime(no performance regression but program is 320KB larger)
E:4: P:230.000000: A:920
E:6: P:64.666667: A:388
E:9: P:58.666667: A:528
E:13: P:67.076923: A:872
E:19: P:69.263158: A:1316
E:28: P:66.285714: A:1856
E:42: P:66.857143: A:2808
E:63: P:61.523810: A:3876
E:94: P:61.404255: A:5772
E:141: P:65.929078: A:9296
E:211: P:69.952607: A:14760
E:316: P:71.417722: A:22568
E:474: P:76.902954: A:36452
E:711: P:79.099859: A:56240
E:1066: P:84.671670: A:90260
E:1599: P:90.346467: A:144464
E:2398: P:93.150959: A:223376
E:3597: P:99.667501: A:358504
E:5395: P:102.829286: A:554764
E:8092: P:109.384083: A:885136
E:12138: P:114.069204: A:1384572
E:18207: P:117.631460: A:2141716
E:27310: P:123.278506: A:3366736
E:40965: P:134.642060: A:5515612
E:61447: P:132.959786: A:8169980
E:92170: P:139.548790: A:12862212
E:138255: P:146.640020: A:20273716
E:207382: P:155.550935: A:32258464
E:311073: P:164.510453: A:51174760
E:466609: P:176.523273: A:82367348
E:699913: P:198.358379: A:138833608
E:1049869: P:210.121945: A:220600516
E:1574803: P:229.066559: A:360734704
E:2362204: P:241.531328: A:570546268
E:3543306: P:248.375581: A:880070688
E:5314959: P:263.173116: A:1398754324
E:7972438: P:277.945011: A:2215899364
E:11958657: P:287.413281: A:3437076840
E:17937985: P:298.343947: A:5351689248
E:26906977: P:301.462868: A:8111454452
E:40360465: P:312.428754: A:12609769776
E:60540697: P:324.866250: A:19667629224
E:90811045: P:333.516035: A:30286939636
E:136216567: P:344.696458: A:46953368176
E:204324850: P:353.691742: A:72268012040
E:306487275: P:364.808772: A:111809246460
E:459730912: P:377.990160: A:173773761152

lasersort theory

uses a two-pass intersect per peak(high / low) where known peaks higher/lower than new peaks are known to be maximums / minimums
--> x = new peak
xoxoooxoxoooooxoooooooox
m = known peak <--
ooooxooooxoooomxooooxoxm

nice

Sort these dubs.

>randperm(10) 8 2 4 7 9 3 5 6 10 1

->
S0 <[8]> <2> 4 7 [9] 3 5 6 [10] <1>

<-
{[8]} {<2>} 4 7 {[9]} <3> <5> <[6]> {<[10]>} {<[1]>} S1 (first active pass)

(1,2,,8,9,10)

missed the [7]

->
S2 8 2 <[4]> {[7]} 9 {<3>} [5] {[6]} 10 1

(1,2,(3,,6,7),8,9,10)

laser-sort extremum trees

     2 - 1
    /
S0 8
    \
     9 - 10

  {2} - 3 - 5
             \
              6 - {10} - {1} S1
             /
{8} - 7 - {9}

>randperm(10) 8 2 4 7 9 3 5 6 10 1

first subpeak ##v0.4?

        1
      /
     2  3
    /  /
S0 8  4
    \  \
     9  7
      \
        10

    {2} - 3
           \   
            5
             \
          4   6 - {10} - {1} S1
             /
           {9}
          /
   {8} - 7 

Fibonacci Buttsort

So
What wins?

>>28

Bogosort

>>28
Radix sort on anything larger than L1 cache.

dubs

sort


proc check(n: int): bool =
n != 0 and n mod 10 == n div 10 mod 10

proc dubssort(arr: var openarray[int]) =
var a = 0
for i in 0..arr.high:
if arr[i].check:
swap arr[i], arr[a]
a += 1

let lim = a - 1
for i in 0..lim:
for j in i..lim:
if arr[i] > arr[j]:
swap arr[i], arr[j]


>>33
very good