pub fn pdqContext(a: usize, b: usize, context: anytype) void {
// slices of up to this length get sorted using insertion sort.
const max_insertion = 24;
// number of allowed imbalanced partitions before switching to heap sort.
const max_limit = if (b > a) math.log2_int(usize, b - a) else 0;
// set upper bound on stack memory usage.
const Range = struct { a: usize, b: usize, limit: usize, leftmost: bool };
var stack: [2 * @bitSizeOf(usize)]Range = undefined;
var range = Range{ .a = a, .b = b, .limit = max_limit, .leftmost = true };
var top: usize = 0;
while (true) {
var was_balanced = true;
var was_partitioned = true;
while (true) {
const len = range.b - range.a;
// very short slices get sorted using insertion sort.
if (len <= max_insertion) {
if (range.leftmost) {
break sort.insertionContext(range.a, range.b, context);
} else {
break unguardedInsertionContext(range.a, range.b, context);
}
}
// if too many bad pivot choices were made, simply fall back to heapsort in order to
// guarantee O(n*log(n)) worst-case.
if (range.limit == 0) {
break sort.heapContext(range.a, range.b, context);
}
// if the last partitioning was imbalanced, try breaking patterns in the slice by shuffling
// some elements around. Hopefully we'll choose a better pivot this time.
if (!was_balanced) {
breakPatterns(range.a, range.b, context);
range.limit -= 1;
}
// choose a pivot and try guessing whether the slice is already sorted.
var pivot: usize = 0;
var hint = chosePivot(range.a, range.b, &pivot, context);
if (hint == .decreasing) {
// The maximum number of swaps was performed, so items are likely
// in reverse order. Reverse it to make sorting faster.
reverseRange(range.a, range.b, context);
pivot = (range.b - 1) - (pivot - range.a);
hint = .increasing;
}
// if the last partitioning was decently balanced and didn't shuffle elements, and if pivot
// selection predicts the slice is likely already sorted...
if (was_balanced and was_partitioned and hint == .increasing) {
// try identifying several out-of-order elements and shifting them to correct
// positions. If the slice ends up being completely sorted, we're done.
if (partialInsertionSort(range.a, range.b, context)) break;
}
// if the chosen pivot is equal to the predecessor, then it's the smallest element in the
// slice. Partition the slice into elements equal to and elements greater than the pivot.
// This case is usually hit when the slice contains many duplicate elements.
if (range.a > a and !context.lessThan(range.a - 1, pivot)) {
range.a = partitionEqual(range.a, range.b, pivot, context);
continue;
}
// partition the slice.
var mid = pivot;
was_partitioned = partition(range.a, range.b, &mid, context);
const left_len = mid - range.a;
const right_len = range.b - mid;
const balanced_threshold = len / 8;
if (left_len < right_len) {
was_balanced = left_len >= balanced_threshold;
stack[top] = .{ .a = range.a, .b = mid, .limit = range.limit, .leftmost = range.leftmost };
top += 1;
range.a = mid + 1;
range.leftmost = false;
} else {
was_balanced = right_len >= balanced_threshold;
stack[top] = .{ .a = mid + 1, .b = range.b, .limit = range.limit, .leftmost = false };
top += 1;
range.b = mid;
}
}
top = math.sub(usize, top, 1) catch break;
range = stack[top];
}
}
Unstable in-place sort. O(n) best case, O(n*log(n)) worst case and average case. O(log(n)) memory (no allocator required).
contextmust have methodsswapandlessThan, which each take 2usizeparameters indicating the index of an item. Sorts in ascending order with respect tolessThan.