sort
lib.lists.sort
Nixpkgs manual
Sort a list based on a comparator function which compares two elements and returns true if the first argument is strictly below the second argument. The returned list is sorted in an increasing order. The implementation does a quick-sort.
See also sortOn, which applies the
default comparison on a function-derived property, and may be more efficient.
Inputs
comparator-
1. Function argument
list-
2. Function argument
Type
sort :: (a -> a -> Bool) -> [a] -> [a]
Examples
lib.lists.sort usage example
sort (p: q: p < q) [ 5 3 7 ]
=> [ 3 5 7 ]
Nix manual
Takes 2 arguments
comparator, list
Return list in sorted order. It repeatedly calls the function
comparator with two elements. The comparator should return true
if the first element is less than the second, and false otherwise.
For example,
builtins.sort builtins.lessThan [ 483 249 526 147 42 77 ]
produces the list [ 42 77 147 249 483 526 ].
This is a stable sort: it preserves the relative order of elements deemed equal by the comparator.
comparator must impose a strict weak ordering on the set of values in the list. This means that for any elements a, b and c from the list, comparator must satisfy the following relations:
- Transitivity
If a is less than b and b is less than c, then it follows that a is less than c.
comparator a b && comparator b c -> comparator a c
- Irreflexivity
comparator a a == false
- Transitivity of equivalence
First, two values a and b are considered equivalent with respect to the comparator if:
!comparator a b && !comparator b a
In other words, neither is considered "less than" the other.
Transitivity of equivalence means:
If a is equivalent to b, and b is equivalent to c, then a must also be equivalent to c.
let
equiv = x: y: (!comparator x y && !comparator y x);
in
equiv a b && equiv b c -> equiv a c
If the comparator violates any of these properties, then builtins.sort
reorders elements in an unspecified manner.
Time Complexity
O(n log n * T_cmp), where:
n = list length
T_cmp = comparator call evaluation time
Uses an adaptive sort that exploits existing sorted runs in the input, down to O(n * T_cmp) when the list is already sorted.
Noogle detected
Implementation
This function is implemented in c++ and is part of the native nix runtime.
static void prim_sort(EvalState & state, const PosIdx pos, Value ** args, Value & v)
{
state.forceList(*args[1], pos, "while evaluating the second argument passed to builtins.sort");
auto len = args[1]->listSize();
if (len == 0) {
v = *args[1];
return;
}
state.forceFunction(*args[0], pos, "while evaluating the first argument passed to builtins.sort");
auto list = state.buildList(len);
for (const auto & [n, v] : enumerate(list))
state.forceValue(*(v = args[1]->listView()[n]), pos);
auto comparator = [&](Value * a, Value * b) {
/* Optimization: if the comparator is lessThan, bypass
callFunction. */
if (args[0]->isPrimOp()) {
auto ptr = args[0]->primOp()->impl.get_fn().target<decltype(&prim_lessThan)>();
if (ptr && *ptr == prim_lessThan)
return CompareValues(state, noPos, "while evaluating the ordering function passed to builtins.sort")(
a, b);
}
Value * vs[] = {a, b};
Value vBool;
state.callFunction(*args[0], vs, vBool, noPos);
return state.forceBool(
vBool, pos, "while evaluating the return value of the sorting function passed to builtins.sort");
};
/* NOTE: Using custom implementation because std::sort and std::stable_sort
are not resilient to comparators that violate strict weak ordering. Diagnosing
incorrect implementations is a O(n^3) problem, so doing the checks is much more
expensive that doing the sorting. For this reason we choose to use sorting algorithms
that are can't be broken by invalid comprators. peeksort (mergesort)
doesn't misbehave when any of the strict weak order properties is
violated - output is always a reordering of the input. */
peeksort(list.begin(), list.end(), comparator);
v.mkList(list);
}
Implementation
The following is the current implementation of this function.
sort = builtins.sort;