Fast Sorting
Also known as: sorting quicksort counting sort performance algorithm complexity big o nlogn
● Advanced3 minBefore this: Sorting
Long lists of whole numbers sort with a radix sort, a few passes by digit instead of comparing pairs, with buckets on every core.
17045759080224266
step 1 of 7
Eight numbers to sort. A radix sort never compares two numbers: it sorts by one digit at a time.
fn main() {
const sorted = [3, 1, 4, 1, 5, 9, 2, 6].sort()
print(sorted)
print(sorted.first() ?? 0)
print([-5, 3, -1_000_000_000_000, 7, 0].sort())
}The program ran and printed:
kavach run numbers.kav
[1, 1, 2, 3, 4, 5, 6, 9]1[-1000000000000, -5, 0, 3, 7]
The same sort() you always write: the algorithm is chosen for you. Text and floats need comparing, so they use a stable merge sort. Which algorithm runs for which list, and why, is on Sorting.
Go deeper the why, for readers who want it
sort — 5M integers · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Go 1.23 · .NET 8 (C# start-up included) · best of 9
Kavach32 ms · finished 1st
C++ -O2361 ms · 11× behind
Go450 ms · 14× behind
C#572 ms · 18× behind
Verify it
git clone https://github.com/Mithlesh04/kavach && cd kavach
sh scripts/run-benchmarks.sh "" benchmarks/loops