Zort

Implementation of 13 sorting algorithms in Zig

| Algorithm | Custom Comparison | Zero Allocation | | ----------------------- | ----------------- | --------------- | | Bubble | ✅ | ✅ | | Comb | ✅ | ✅ | | Heap | ✅ | ✅ | | Insertion | ✅ | ✅ | | Merge | ✅ | ❌ | | PDQ | ✅ | ✅ | | Quick | ✅ | ✅ | | Radix (no negative yet) | ❌ | ❌ | | Selection | ✅ | ✅ | | Shell | ✅ | ✅ | | Tail | ✅ | ❌ | | Tim | ✅ | ❌ | | Twin | ✅ | ❌ |

Usage

const zort = @import("zort");

fn asc(a: u8, b: u8) bool {
    return a < b;
}

pub fn main() !void {
    var arr = [_]u8{ 9, 1, 4, 12, 3, 4 };
    try zort.quickSort(u8, &arr, asc);
}

Benchmarks

Intel(R) Core(TM) i7-4600U CPU @ 2.10GHz

gantt
    title Sorting (ascending) 10000000 usize
    dateFormat x
    axisFormat %S s
    section random
    tim 1.932: 0,1932
    pdq 0.400: 0,400
    quick 0.882: 0,882
    radix 0.311: 0,311
    twin 1.126: 0,1126
    std_block_merge 1.402: 0,1402
    comb 1.631: 0,1631
    shell 2.943: 0,2944
    section sorted
    tim 0.010: 0,10
    pdq 0.011: 0,11
    quick 0.281: 0,281
    radix 0.303: 0,303
    twin 0.085: 0,85
    std_block_merge 0.063: 0,63
    comb 0.500: 0,500
    shell 0.332: 0,332
    section reverse
    tim 0.603: 0,603
    pdq 0.108: 0,108
    quick 0.474: 0,474
    radix 0.251: 0,251
    twin 0.431: 0,431
    std_block_merge 0.477: 0,477
    comb 0.559: 0,559
    shell 0.357: 0,357
    section ascending saw
    tim 0.325: 0,325
    pdq 0.408: 0,408
    quick 1.454: 0,1454
    radix 0.318: 0,318
    twin 0.285: 0,285
    std_block_merge 0.518: 0,518
    comb 0.836: 0,836
    shell 0.590: 0,590
    section descending saw
    tim 0.482: 0,482
    pdq 0.404: 0,404
    quick 49.500: 0,49519
    radix 0.375: 0,375
    twin 0.674: 0,674
    std_block_merge 0.746: 0,746
    comb 1.082: 0,1082
    shell 0.834: 0,834

gantt
    title Sorting (ascending) 10000000 isize
    dateFormat x
    axisFormat %S s
    section random
    tim 2.160: 0,2160
    pdq 0.515: 0,515
    quick 0.987: 0,987
    radix 0.407: 0,407
    twin 1.281: 0,1281
    std_block_merge 1.588: 0,1588
    comb 1.753: 0,1753
    shell 2.480: 0,2481
    section sorted
    tim 0.013: 0,13
    pdq 0.013: 0,13
    quick 0.207: 0,207
    radix 0.212: 0,212
    twin 0.086: 0,86
    std_block_merge 0.090: 0,90
    comb 0.681: 0,681
    shell 0.442: 0,442
    section reverse
    tim 0.029: 0,29
    pdq 0.053: 0,53
    quick 0.424: 0,424
    radix 0.188: 0,188
    twin 0.020: 0,20
    std_block_merge 0.393: 0,393
    comb 0.544: 0,544
    shell 0.355: 0,355
    section ascending saw
    tim 0.417: 0,417
    pdq 0.522: 0,522
    quick 0.668: 0,668
    radix 0.234: 0,234
    twin 0.312: 0,312
    std_block_merge 0.452: 0,452
    comb 0.899: 0,899
    shell 0.688: 0,688
    section descending saw
    tim 0.339: 0,339
    pdq 0.422: 0,422
    quick 33.281: 0,33269
    radix 0.250: 0,250
    twin 0.373: 0,373
    std_block_merge 0.797: 0,797
    comb 1.001: 0,1001
    shell 0.699: 0,699

Big Thank to

voroskoi and other contributors

Package Contents

• .gitattributes
• benchmark/run_bench.zig
• benchmark/generator.zig
• LICENSE
• build.zig
• benchmark.sh
• zigmod.yml
• src/insertion.zig
• src/tim.zig
• src/radix.zig
• src/bubble.zig
• src/merge.zig
• src/shell.zig
• src/tail.zig
• src/pdqsort.zig
• src/selection.zig
• src/main.zig
• src/test.zig
• src/heap.zig
• src/twin.zig
• src/quick.zig
• src/comb.zig
• README.md
• media/logo.png
• media/logo.fig
• .gitignore

History

	Published On	Tree @ Commit	Size
v0.36	Sun, 08 Jan 2023 17:33:17 UTC	Tree	122.073 KB
v0.35	Sat, 29 Oct 2022 19:29:33 UTC	Tree	121.987 KB
v0.34	Thu, 22 Sep 2022 19:25:40 UTC	Tree	114.859 KB
v0.33	Sat, 27 Aug 2022 03:47:22 UTC	Tree	118.303 KB
v0.32	Mon, 22 Aug 2022 18:21:47 UTC	Tree	117.782 KB
v0.31	Mon, 08 Aug 2022 21:38:40 UTC	Tree	117.778 KB
v0.30	Sat, 06 Aug 2022 09:53:24 UTC	Tree	88.812 KB
v0.29	Fri, 05 Aug 2022 12:07:15 UTC	Tree	82.142 KB
v0.28	Fri, 05 Aug 2022 11:10:58 UTC	Tree	56.816 KB
v0.27	Fri, 05 Aug 2022 11:08:02 UTC	Tree	56.822 KB
v0.26	Mon, 01 Aug 2022 19:46:11 UTC	Tree	54.825 KB
v0.25	Mon, 01 Aug 2022 06:11:13 UTC	Tree	49.457 KB
v0.24	Mon, 01 Aug 2022 06:09:33 UTC	Tree	49.668 KB
v0.23	Sat, 30 Jul 2022 22:35:53 UTC	Tree	49.218 KB
v0.22	Sat, 30 Jul 2022 20:57:59 UTC	Tree	49.386 KB
v0.21	Sat, 30 Jul 2022 20:43:16 UTC	Tree	49.209 KB
v0.20	Thu, 28 Jul 2022 20:32:09 UTC	Tree	44.887 KB
v0.19	Sun, 17 Jul 2022 06:36:58 UTC	Tree	29.603 KB
v0.18	Thu, 19 May 2022 15:22:44 UTC	Tree	27.198 KB
v0.17	Thu, 19 May 2022 15:17:40 UTC	Tree	27.758 KB
v0.16	Thu, 19 May 2022 15:08:25 UTC	Tree	27.285 KB
v0.15	Thu, 19 May 2022 14:10:51 UTC	Tree	27.107 KB
v0.14	Sat, 07 May 2022 05:36:29 UTC	Tree	29.861 KB
v0.13	Wed, 04 May 2022 14:45:20 UTC	Tree	29.380 KB
v0.12	Mon, 02 May 2022 10:54:12 UTC	Tree	61.833 KB
v0.11	Mon, 02 May 2022 10:49:59 UTC	Tree	61.833 KB
v0.10	Sat, 23 Apr 2022 15:57:47 UTC	Tree	52.633 KB
v0.9	Sun, 20 Mar 2022 18:47:44 UTC	Tree	52.641 KB
v0.8	Sun, 20 Mar 2022 11:38:52 UTC	Tree	52.973 KB
v0.7	Fri, 18 Mar 2022 16:32:02 UTC	Tree	50.603 KB
v0.6	Fri, 18 Mar 2022 16:31:29 UTC	Tree	50.733 KB
v0.5	Fri, 18 Mar 2022 16:27:12 UTC	Tree	50.733 KB
v0.4	Fri, 18 Mar 2022 16:24:57 UTC	Tree	50.765 KB
v0.3	Fri, 18 Mar 2022 16:21:29 UTC	Tree	50.672 KB
v0.2	Thu, 17 Mar 2022 11:35:28 UTC	Tree	19.215 KB
v0.1	Wed, 16 Mar 2022 16:50:48 UTC	Tree	19.215 KB