insertionContext

Stable in-place sort. O(n) best case, O(pow(n, 2)) worst case. O(1) memory (no allocator required). context must have methods swap and lessThan, which each take 2 usize parameters indicating the index of an item. Sorts in ascending order with respect to lessThan.

Function parameters

Parameters

a:usize
b:usize
context:anytype

Type definitions in this namespace

Types

Mode

Functions in this namespace

Functions

block
pdq
pdqContext
insertion: Stable in-place sort.
insertionContext: Stable in-place sort.
heap: Unstable in-place sort.
heapContext: Unstable in-place sort.
asc: Use to generate a comparator function for a given type.
desc: Use to generate a comparator function for a given type.
binarySearch: Returns the index of an element in `items` returning `.eq` when given to `compareFn`.
lowerBound: Returns the index of the first element in `items` that is greater than or equal to `context`,
upperBound: Returns the index of the first element in `items` that is greater than `context`, as determined
partitionPoint: Returns the index of the partition point of `items` in relation to the given predicate.
equalRange: Returns a tuple of the lower and upper indices in `items` between which all
argMin
min
argMax
max
isSorted

Source

Implementation

pub fn insertionContext(a: usize, b: usize, context: anytype) void {
    assert(a <= b);

    var i = a + 1;
    while (i < b) : (i += 1) {
        var j = i;
        while (j > a and context.lessThan(j, j - 1)) : (j -= 1) {
            context.swap(j, j - 1);
        }
    }
}