Sorting

Marrow picks a sort by input type and size: for primitive arrays, a pattern-defeating quicksort for small inputs and an LSD radix sort for large ones; a comparison sort for strings; a counting sort for booleans. Nulls are ordered explicitly — you choose whether they sort to the front or the back.

Sorting an array

mc.sort returns a sorted copy; the array’s .argsort() method (or mc.sort_indices) returns the indices that would sort it (an int32 array), leaving the input untouched:

a = ma.array([3, 1, None, 2, 5])

print("sorted:      ", mc.sort(a))
print("argsort:     ", a.argsort())
print("sort_indices:", mc.sort_indices(a))
sorted:       PrimitiveArray[int64]([1, 2, 3, 5, NULL])
argsort:      PrimitiveArray[int32]([1, 3, 0, 4, 2])
sort_indices: PrimitiveArray[int32]([1, 3, 0, 4, 2])

Direction and null placement

sort and sort_indices take a sort_keys sequence of (column, order) pairs — for a plain array the column name is ignored, the first key’s direction is used, and more than one key raises NotImplementedError — and a null_placement keyword argument:

print(mc.sort(a, [("", "ascending")],  null_placement="at_start"))
print(mc.sort(a, [("", "ascending")],  null_placement="at_end"))
print(mc.sort(a, [("", "descending")], null_placement="at_end"))
PrimitiveArray[int64]([NULL, 1, 2, 3, 5])
PrimitiveArray[int64]([1, 2, 3, 5, NULL])
PrimitiveArray[int64]([5, 3, 2, 1, NULL])
Argument Values Default
sort_keys [(column, "ascending" \| "descending")] () (ascending)
null_placement "at_start" / "at_end" "at_end"

Sorting works across types — strings order lexicographically:

words = ma.array(["pear", "apple", None, "cherry"])
print(mc.sort(words, null_placement="at_end"))
StringArray([apple, cherry, pear, NULL])

Sorting a table

RecordBatch.sort_by reorders whole rows by a key column. Pass a list of (column, "ascending" | "descending") tuples and a null-placement argument (None for the default):

people = ma.record_batch({
    "name": ma.array(["Alice", "Bob", "Carol", "Dave"]),
    "age":  ma.array([34, 28, 45, 28]),
})

print(people.sort_by([("age", "ascending")]).to_pylist())
[{'name': 'Bob', 'age': 28}, {'name': 'Dave', 'age': 28}, {'name': 'Alice', 'age': 34}, {'name': 'Carol', 'age': 45}]

Multi-column keys work from Python too — ties on the first key break on the next, and each key carries its own direction:

print(people.sort_by([("age", "ascending"), ("name", "descending")]).to_pylist())
[{'name': 'Dave', 'age': 28}, {'name': 'Bob', 'age': 28}, {'name': 'Alice', 'age': 34}, {'name': 'Carol', 'age': 45}]

sort_by also accepts a num_threads argument (0 auto-selects cores, 1 forces the serial path) for large batches.

Under the hood — the Mojo sort kernel

At the Mojo level, sort_indices returns the permutation for a single array and take applies it to get a sorted copy. Both take a type-erased DynArray; call SortIndices.apply / TakeKernel.apply when you already hold a typed array.

from marrow.kernels.sort import sort_indices
from marrow.kernels.filter import take
from marrow.builders import array
from marrow.dtypes import int64

var values = array([3, 1, 4, 1, 5, 9, 2, 6], int64)

# Indices that would sort the array
var idx = sort_indices(values.copy(), ascending=True, nulls_first=True)

# A sorted copy
var ordered = take(values.copy(), idx)

Multi-column sort operates on a StructArray, ordering rows by a list of key column indices with a per-key ascending flag:

from marrow.kernels.sort import sort

# rows sorted by column 0 ascending, ties broken by column 1 descending
var ordered = sort(struct_array, key_indices=[0, 1], ascending=[True, False])

Algorithm selection

For primitive arrays, the strategy switches at fixed sizes:

Input size Strategy
N < 32,768 PDQsort (pattern-defeating quicksort)
N ≥ 32,768 LSD radix sort
N ≥ 524,288 Parallel radix sort, given a multi-threaded context

The thresholds are fixed rather than tuned per machine, and they are not the fastest choice at every size. mc.sort and mc.sort_indices run single-threaded unless you pass a multi-threaded ctx.

Back to top