quick_sort

Sorts an array in place and returns the same view, so calls can be chained.

There are two forms. quick_sort(array, compare) takes a three-way comparator, compare(a, b) returning a negative number when a goes first, zero when they tie and a positive number otherwise (any numeric return type will do). It is an introsort: quicksort that falls back to heap sort on bad input, so it is O(n log n) in the worst case, and it does not keep the order of equal elements. quick_sort(array, key) takes a procedure that gives each element a key compared with <; the key is computed once per element, and elements with equal keys do keep their order (it is stable). That form allocates a temporary copy with context.allocator and frees it before returning.

A comparator should be consistent (a strict weak order). An inconsistent one gives an unspecified order, but the sort stays within the array and always finishes. Arrays of fewer than two elements are returned untouched.

Person :: struct { name: string; age: int; }
people := Person.[.{"Ann", 31}, .{"Bo", 25}, .{"Cy", 31}];

by_age :: (a: Person, b: Person) -> int { return a.age - b.age; }
quick_sort(people, by_age);
assert(people[0].name == "Bo");

age_of :: (p: Person) -> int { return p.age; }
quick_sort(people, age_of);   // stable: Ann stays before Cy
assert(people[1].name == "Ann" && people[2].name == "Cy");

numbers := int.[3, 1, 2];
sorted := quick_sort(numbers, (a: int, b: int) -> int { return a - b; });
assert(sorted[0] == 1 && sorted[2] == 3 && sorted.data == numbers.data);

quick_sort :: (array: [] $T, f: (T, T) -> $R) -> [] T

quick_sort :: (array: [] $T, f: (T) -> $R) -> [] T