sort.h

#include <sif/utils/sort.h>

SIF_UTILS_SORT_H

Type-specialized quicksort, generated by macro.

Generated rather than passed a comparison function pointer: these sorts run on arrays of millions of scalars, where an indirect call per comparison costs more than the comparison, and inlining the predicate is what lets the partition loop stay in registers.

SIF_DEFINE_QUICKSORT(function_name, type, less_than_expr)

Define a quicksort over type at file scope.

Expands to a pair of static functions: the entry point function_name, taking (type* arr, uint64_t count), and its recursive helper. Place it at file scope in a .c, once per (type, order) pair needed:

SIF_DEFINE_QUICKSORT(sort_radii_desc, sif_real, a > b)
SIF_DEFINE_QUICKSORT(sort_real_asc,   sif_real, a < b)
...
sort_radii_desc(radii, n);

Parameters:

• function_name – Name of the generated entry point.

• type – Element type, sorted by value.

• less_than_expr – Ordering predicate, written in terms of two variables named `a` and `b` that the macro declares for you. It must be a strict weak ordering: a < b for ascending, a > b for descending.

Note

The predicate is evaluated twice per element, once as given and once with the operands exchanged, to obtain both “less” and “greater” from a single expression. This is what makes the partition three-way, so runs of equal keys are placed in one pass instead of being repeatedly re-partitioned – the right trade for radius arrays, which are full of ties.

Warning

Recursion is not depth-limited and the larger partition is not eliminated by a tail call, so a pathological input costs stack proportional to the element count. The pivot is the middle element, which makes sorted and reverse-sorted input the good case rather than the bad one, but an adversarial ordering is not defended against.