ddn.columnar.sort

The sort layer of ddn.df: stable argument sorts over (key, idx) pairs with the index tie-break always applied (D17; ADR-2026-10-18-13).

Every sort is stable, single and multi-key: ties are broken on the original index, at the measured cost of about ten per cent over an unstable sort (fact 12). Nulls partition out of the key sort and go first by default. Floats use a total order in which NaN equals NaN and is greatest and -0.0 equals 0.0 (D12); eq stays IEEE. Multi-key sorts run one stable pass per key, last key first, so earlier passes become the tie-break of later ones. * Implements ADR-2026-10-18-19 (amending ADR-2026-10-18-13: the fixed-width kinds sort through a stable radix over order-preserving keys).

Copyright

License

BSD-3-Clause

var SEGMENT_MATRIX_BUDGET

enum RankMethod

fn argSortBits argSortKernel argSortOf argSortPairs argSortRadix bitsOf cmp cmpStr cmpTotal compareValues equalKeys locateIn lsdOrder64 multiKeyArgSort radixKey rankOf rowCompare rowsEqualKeys scatterByCode splitValid stablePass totalLess totalSort

Types 1

enumRankMethod

The rank tie methods (ADR-2026-10-23-11), Polars' names.

AVERAGEThe mean of the tied positions (FLOAT64 output).

MINThe lowest tied position.

MAXThe highest tied position.

FIRSTTies keep their original row order.

ORDINALDistinct positions in original row order.

DENSEPositions count distinct values, not rows.

Functions 24

size_t[] argSortOf(Series series,  bool  descending =  false,
       bool  nullsLast =  false)

Sorts the indices of a Series by its values.

private fn

size_t[] argSortKernel(Kind K)(ArrayData[]  chunks,  bool  descending,
       bool  nullsLast)

private fnulong radixKey(Kind K)(PhysicalOf!K value) @safe pure nothrowThe order-preserving unsigned key of one valid value: the total order of the physical type maps onto the unsigned order - NaN greatest and all NaNs one key, `-0.0` equal to `0.0`, signed integers b...

private fnulong bitsOf(double v) @safe pure nothrowThe IEEE-754 bit pattern of a floating value through a union bitcast (no alignment or aliasing hazards at this width).

private fnuint bitsOf(float v) @safe pure nothrowDitto, at `float` width.

private fn

size_t[] argSortRadix(Kind K)(ArrayData[]  chunks,  bool  descending,
       bool  nullsLast)

The stable radix path: collects the valid slots' radix keys and original indices, then LSD-sorts by 8-bit digits, skipping the passes whose digit is constant. Stability keeps equal keys in original...

private fn

size_t[] argSortBits(ArrayData[]  chunks,  bool  descending,
       bool  nullsLast)

The BOOLEAN path: a two-bucket count in scan order - stability for free, no comparisons at all.

private fnvoid lsdOrder64(ref ulong[] radix, ref size_t[] order)The STRING path: the preallocated (key, idx) pair sort with the idx tie-break always applied (D17) - string comparisons stay memcmp bound, so the allocation fix is the win here.

private fn

size_t[] argSortPairs(Kind K)(ArrayData[]  chunks,  bool  descending,
       bool  nullsLast)

private fnvoid totalSort(alias less, T)(ref T[] arr)Sorts `arr` under a total order: segments sort in parallel, then pairwise merge rounds run in parallel. A total order has exactly one sorted permutation, so the result is identical to a serial sort...

private fnauto splitValid(Kind K)(ArrayData[] chunks)Splits one key column into its valid entries' keys and rows and its null rows, sized exactly in one counting pass and filled densely per chunk (one view per chunk, never per element).

fnbool totalLess(T)(T a, T b) @safe pure nothrowThe total order for floats: NaN greatest, `-0.0` equal to `0.0` (D12) - shared by the sort paths and the grouped min/max.

private fnbool equalKeys(T)(T a, T b) @safe pure nothrow

size_t[] multiKeyArgSort(Series[]  keys,  bool[]  descending,
       bool  nullsLast =  false)

Sorts rows by several key columns at once: one stable pass per key, last key first, so earlier keys become the tie-break of later ones. Every pass applies the null placement. This is the column-inp...

Series rankOf(Series series,  RankMethod method =  RankMethod.AVERAGE,
       bool  descending =  false)

Ranks the valid values under the total order (ADR-2026-10-23-11): 1-based; ties receive the method's position; null slots stay null; `descending` reverses the value order, not the tie semantics (`F...

private fn

bool rowsEqualKeys(const(ArrayData)[]  chunks,
       const  size_t[]  starts,  size_t a,  size_t b,  ColumnEq eq)

@safe pure nothrow

private fnsize_t locateIn(const size_t[] starts, size_t row) @safe pure nothrow

private fn

void stablePass(Series key,  ref  size_t[]  perm,  bool  descending,
       bool  nullsLast)

private fn

void scatterByCode(const(uint)[]  code,  uint  runs,
       ref  size_t[]  perm)

int rowCompare(Series key,  size_t a,  size_t b,  bool  descending,
       bool  nullsLast)

private fnint compareValues(Series key, size_t a, size_t b)

private fnint cmp(T)(T a, T b) @safe pure nothrow

private fnint cmpStr(string a, string b) @safe pure nothrow

private fnint cmpTotal(T)(T a, T b) @safe pure nothrow

Variables 1

private enumvarSEGMENT_MATRIX_BUDGET = 16U << 20