search

alichraghi / zort

Sorting algorithms in zig
MIT License
61 stars 6 forks source link

Add twinSort and tailSort #3

Closed voroskoi closed 2 years ago

voroskoi commented 2 years ago

Hi,

I have made this to see if it is really as fast as Timsort, but my results are much worse. Well, my benchmark results are completely different than Yours, have no idea why.

These results are from a rpi4, but a x86_64 laptop gives similar results. Timsort beats them all.

```json { "results": [ { "command": "../zig-out/bin/run_bench quick", "mean": 7.514543614600001, "stddev": 0.056532603782643166, "median": 7.510637083000001, "user": 6.5218869, "system": 0.9763834000000001, "min": 7.451953318, "max": 7.612106793, "times": [ 7.459466894, 7.544153477, 7.451953318, 7.593717209, 7.528130463, 7.5219761510000005, 7.612106793, 7.477700925, 7.456932901, 7.499298015 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench tim", "mean": 2.8738921488, "stddev": 0.00912521352392666, "median": 2.874949392, "user": 0.8643097, "system": 1.9997140999999998, "min": 2.860141913, "max": 2.887493912, "times": [ 2.887493912, 2.876989623, 2.864580723, 2.883735818, 2.860141913, 2.881046029, 2.871758691, 2.877103919, 2.863161699, 2.872909161 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench comb", "mean": 13.1305741924, "stddev": 0.2077359613029529, "median": 13.0576987715, "user": 12.1441363, "system": 0.9805217, "min": 12.905284575, "max": 13.449826538, "times": [ 13.41255317, 13.060204581, 13.449826538, 12.905284575, 12.914950835, 13.307535651, 12.963872313, 12.977345629, 13.25897567, 13.055192962 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench shell", "mean": 18.8838240842, "stddev": 0.21378568611389104, "median": 18.8655576055, "user": 17.8355127, "system": 0.9804465999999998, "min": 18.475947382, "max": 19.227700796, "times": [ 19.227700796, 18.855733456, 18.875381755, 18.941397799, 19.121245788, 18.705116313, 18.76706638, 19.022389462, 18.475947382, 18.846261711 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench heap", "mean": 30.935127389799998, "stddev": 0.1179879294352556, "median": 30.9131563605, "user": 29.9546504, "system": 0.9726389999999998, "min": 30.736613401, "max": 31.176322164, "times": [ 31.176322164, 31.011362759, 30.736613401, 30.962533885, 30.888262651, 30.93805007, 31.018861902, 30.876430851, 30.884933835, 30.85790238 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench radix", "mean": 6.537990938599999, "stddev": 0.33984714527455834, "median": 6.3561714480000004, "user": 4.0851091, "system": 2.4496874999999996, "min": 6.189218341, "max": 6.9877329800000005, "times": [ 6.300387852, 6.189218341, 6.255382828, 6.22384379, 6.96090269, 6.9877329800000005, 6.394630764, 6.3177121320000005, 6.927000845, 6.823097164 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench std_block_merge", "mean": 10.8066206889, "stddev": 0.015478303577227065, "median": 10.811080628500001, "user": 9.763933999999999, "system": 1.0023389, "min": 10.769447772, "max": 10.823173390000001, "times": [ 10.813647509, 10.799715083, 10.808513748, 10.816093594, 10.80662688, 10.7959484, 10.816297314, 10.823173390000001, 10.816743199, 10.769447772 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench merge", "mean": 862.3499611646, "stddev": 1.6480987236425435, "median": 861.9782927235001, "user": 160.7355188, "system": 701.4973833999999, "min": 860.223807879, "max": 865.224115947, "times": [ 860.223807879, 861.708047336, 862.978492307, 862.248538111, 862.501155304, 864.962681896, 861.335983172, 860.903053422, 861.413736272, 865.224115947 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] }, { "command": "../zig-out/bin/run_bench twin", "mean": 8.600588286699999, "stddev": 0.023282992260490826, "median": 8.599323608999999, "user": 7.5364702999999995, "system": 1.0610411, "min": 8.563701042, "max": 8.642994853, "times": [ 8.642994853, 8.607902078, 8.605584953, 8.563701042, 8.581149811, 8.583078402, 8.615209337, 8.593062265, 8.589074564, 8.624125562 ], "exit_codes": [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] } ] } ```
alichraghi commented 2 years ago

Thank you for contribution. can you post spec details?