Sorting
Also known as: sort order sorted ascending descending alphabetical radix quicksort merge sort stable compare key orderby sort_by case insensitive
● Beginner6 minBefore this: ListsSpec 14.2
list.sort() gives a sorted copy of a list of numbers, text, characters, Bools or tuples. sort_by(key) sorts anything else, by a key you choose.
fn main() {
print([42, -7, 0, 1_000, 3].sort())
const sizes: [UInt8] = [200, 3, 77]
print(sizes.sort())
print([10, 2, 33].sort().reverse())
}The program ran and printed:
kavach run numbers.kav
[-7, 0, 3, 42, 1000][3, 77, 200][33, 10, 2]
Both give a new list and leave the original as it was. For the largest first, add .reverse().
How each type sorts
| Items | Order | More |
|---|---|---|
Int, Int8 … UInt64 | smallest first; negative numbers before 0 | See it → |
Float, Float32 | smallest first; NaN after every number; 0.0 and -0.0 are equal | See it → |
Decimal, BigInt | by exact value, however many digits | See it → |
String | by Unicode code point, character by character: uppercase before lowercase, accented letters after z | See it → |
Char | by Unicode code point | See it → |
Bool | false before true | See it → |
Tuples | item by item: by the first item, then the second when the first are equal, and so on | See it → |
Records, unions | no order of their own: use sort_by with a key | See it → |
A list holds one type, so there is no "mixed" list to sort: [1, "a"] doesn't compile. Data of mixed kinds is a list of records or of a union, sorted by a key you choose.
How whole numbers sort so fast
Comparing pairs of numbers takes about n × log n steps. For a long list of whole numbers, Kavach uses a radix sort instead: it places each number by one digit at a time, in a few passes over the list. Step through it:
Eight numbers to sort. A radix sort never compares two numbers: it sorts by one digit at a time.
Which algorithm runs for which items, and why, is under "Go deeper" below.
One page for each form
Go deeper the why, for readers who want it
Which algorithm
| Sorting | In a program built by Kavach | Why |
|---|---|---|
| Whole numbers and Char, under 512 items | a comparison sort (Rust's unstable sort, a quicksort variant) | for a short list, counting digits costs more than comparing; equal whole numbers can't be told apart, so keeping their order doesn't matter |
| Whole numbers and Char, 512 items or more | a radix sort, 8 bits of each number at a time | a few passes over the list instead of n × log n comparisons; bits that are the same in every number are skipped |
| … 65,536 items or more | first split by the top 8 bits into 256 buckets | each bucket is small enough to sort inside the processor's cache, where memory is fastest |
| … 1,048,576 items or more | the buckets are sorted on all cores at once | the buckets don't depend on each other, so the result is the same in any order |
| Floats, text, Decimal, BigInt, tuples | a stable merge sort (Rust's standard sort) | these need comparing (NaN, text by code point), and equal items, like 0.0 and -0.0, keep their order |
| sort_by | the keys are worked out once each, then sorted with the stable merge sort | your key function runs once per item, not once per comparison, and equal keys keep their order |
kavach run uses the stable merge sort for everything; the results are the same. A million numbers, sorted and checked:
fn main() {
let xs: [Int] = []
for i in 0..1_000_000 {
xs.push((i * 7_919) % 1_000_003 - 500_000)
}
const sorted = xs.sort()
let in_order = true
for i in 1..sorted.len() {
if sorted[i - 1] > sorted[i] {
in_order = false
}
}
print("{sorted.len()} numbers, in order: {in_order}")
print("smallest {sorted[0]}, largest {sorted[sorted.len() - 1]}")
}The program ran and printed:
kavach run large.kav
1000000 numbers, in order: truesmallest -500000, largest 500002
How much faster the radix sort is, against C++'s std::sort, is on Fast Sorting. Sorting runs on the CPU today, not on the GPU.
Check yourself
["banana", "Apple", "apple"].sort() give?