Zig Version

0.11.0-dev.2685+fac120bc3

Steps to Reproduce and Observed Behavior

Reproducible benchmark here:

https://github.com/matklad/benchmarks/tree/2b07628b8bbf5c9258c807aa8a221a0797f247b9/sort

The interesting bits:

Rust + unstable:
424.10ms

Rust + stable:
765.45ms

Zig
1.147s

By itself, the number is not surprising. Zig's sort is both stable and in place, while Rust's stable sort allocates.

However, while stable sort is a good default choice, Zig strives for optimality, so the user should be able to choose better performance if stability is not a requirement.

Expected Behavior

std.sort.sortUnstable exists and it is as fast as state of the art. I noticed that

https://github.com/alichraghi/zort/blob/67493f9412c65526fd0a5db447b52d53e282a934/src/pdqsort.zig

actually is a tiny bit faster than even Rust on my benchmark, so perhaps we can add that to stdlib? cc @alichraghi