MonotonicOrder

Stable radix ordering for monotonic keys, plus a compact O(K) reference distribution model. MonotonicOrder returns reusable permutations instead of moving arbitrary payload objects inside the native kernel.

Why MonotonicOrder

• exact stable argsort for uint64, int64, IEEE-754 float64, datetime, timedelta and UUID keys;
• lexicographic multi-field ordering with per-field direction and missing-value policy;
• variable-length bytes and Unicode ordering without Python comparators in the radix passes;
• explicit Morton 2D/3D and Hilbert 2D spatial-curve keys;
• compact quantile reference state with stored min/max/median/quartiles/MAD;
• C11 core and CPython abi3 extension targeting Python 3.9+.

Is it faster than NumPy?

Honest answer: it depends on whether your ordering is a one-shot or a structure. Measured on this project's benchmark machine (full report with spreads and methodology; reproduce with make benchmark-engine):

Where MonotonicOrder wins:

You want to...	MonotonicOrder	vs NumPy
Get a stable argsort (ties keep input order)	order.argsort(a)	3.5-5x faster than np.argsort(kind="stable"), from 10k elements up
Sort by several columns at once	order.lexargsort(a, b, c)	~3-4x faster than np.lexsort
Ask many order questions about one dataset (median, top-k, ranges...)	order.index(data) once, then O(1)/O(log N) queries	>1000x faster than recomputing; pays for itself by the 2nd query
Find a median/rank without sorting everything	order.select(a, k), warmed by Order.fit	~2x faster than np.median
Keep an index fresh while rows keep arriving	index.merged_with(delta)	~10x faster than re-indexing when keys come from Python objects
Sort objects/records by a key function	order.sort(rows, key=...)	key called exactly once per row, then native speed — no np equivalent
Know which rows matched (not just values), get equal-key groups, spatial curve order	index.between/runs, morton/hilbert_argsort	no direct NumPy equivalent

Where NumPy wins — use it there:

You want to...	Winner	By how much
One-shot sort of a plain float array	np.sort	~1.2x at 10M, more on small arrays
Repeated value-only lookups into one float array	cache np.sort(a) + np.searchsorted	13-46x per query cheaper than our index (which pays for row labels you'd not be using)
Argsort where stability doesn't matter	np.argsort (default quicksort)	faster — we always pay for stability
Sort a handful of short strings	sorted(a)	~2x — CPython's comparator is hard to beat at small N

Every number above comes from ORDER_ENGINE_RESULTS.md, including the ones we lose — the benchmark compares cached operators against cached competitors, states which build ran, and prints run-to-run spreads next to every median.

Read next	Contents
Pure-Python walkthrough	The whole theory in ~400 lines of naive, heavily narrated Python — start here to understand, come back for speed
Theory	Mathematical contracts, exactness boundaries and proofs
Monotonic-key epic	Historical record of the pre-Order delivery (superseded)
Order-engine epic	Unified runtime, indexing and delivery plan (complete, 1.0.0)
Cache-aware kernels epic	Two-level kernel integration, debt cleanup and the 1.1.0 release plan
Order engine results	Reproducible performance measurements
Migration guide	Mapping from the removed standalone helpers to Order
Changelog	Release history
Contributing	Development and verification workflow

The training array is sorted only in temporary construction memory; it is never retained by the finished model.

The complete mathematical specification, proofs of the radix ordering contract, approximation boundary and warmed-object semantics are in THEORY.md.

EPIC_MONOTONIC_KEYS.md is the historical record of the pre-Order delivery; its standalone-function API surface (radix_argsort, order_by, sort, ...) has since been removed in favor of Order — see MIGRATION.md. The current roadmap is EPIC_ORDER_ENGINE.md.

Mathematical contract

The compressed reference operator is

P_K(mu_N) = (q_0, ..., q_K; min, q1, median, q3, max, MAD),

where q_j = F_N^-1(j/K). It provides monotone approximate arbitrary ranks and quantiles. For strictly increasing knots the probability-cell resolution is 1/K; repeated values create intrinsically wider rank intervals. Values at stored quantile knots and the stored scalar statistics are exact.

Exact sorting is a separate universal operator. A finite non-NaN IEEE-754 value is mapped to an unsigned key tau(x) such that

x < y  iff  tau(x) < tau(y).

A stable five-pass radix factorisation (13+13+13+13+12 bits) sorts those keys. The inverse map returns the original values. NaN-containing arrays use the payload-preserving path and place all NaNs last. Therefore correctness does not depend on how closely new data matches the training distribution. Monotone arrays and bounded integer-valued float domains have exact linear fast paths before radix execution.

Exact arbitrary rank/contains queries against discarded training data are intentionally not claimed: those require Omega(N) information in the worst case. rank() and quantile() are named as compressed-reference estimates; all array operations (sort, unique, top_k, bottom_k, count_between, is_sorted) are exact.

Install

From the latest tagged release:

python -m pip install "monotonic-order @ git+https://github.com/dimaq12/monotonic-order.git@v1.2.0"

For local development:

python -m pip install -e ".[test]"
python -m pytest

The distribution name is monotonic-order; the import package is monotonic_order. Installation compiles the bundled C11 core as a platform extension. Portable builds deliberately avoid -march=native. To opt into OpenMP when the compiler and runtime support it:

MONOTONIC_ORDER_OPENMP=1 python -m pip install .

Local source builds may additionally opt into host-specific codegen — a measured ~10% kernel win (EPIC_SORT_PERFORMANCE.md §4.3) at the cost of a non-portable binary, so it is never used for distributed wheels:

MONOTONIC_ORDER_NATIVE=1 python -m pip install .

The native loader uses CPython's stable ABI (abi3) targeting Python 3.9+, so one wheel can serve multiple CPython versions on the same platform.

Migrating from IdealOrder 0.6

Use monotonic_order and MonotonicOrder in new code. Versions 0.7+ keep ideal_order and IdealOrder as compatibility aliases, but the canonical distribution and native C symbols have changed:

# before
from ideal_order import IdealOrder

# 0.7+
from monotonic_order import MonotonicOrder

For C callers, include monotonic_order.h. The compatibility ideal_order.h maps old source names to the new API when recompiling.

Migrating from standalone helpers to Order

radix_argsort, radix_lexargsort, order_by, the module-level sort/ sort_reverse/bottom_k/top_k facade functions, and the corresponding MonotonicOrder.sort/.sort_reverse/.bottom_k/.top_k static methods have been removed — Order is now the single entry point for ordering, with no separate duplicate API. See MIGRATION.md for the full function-by-function mapping. MonotonicOrder.is_sorted/.unique/ .count_between/.exact_quantile and the reference-model statistics (.median, .rank, .quantile, ...) are unaffected — they have no Order duplicate and remain first-class API.

The full engine surface, beyond what the examples below show: Order.argsort/ .lexargsort/.sort/.apply/.select/.median/.minmax/.minimum/ .maximum/.bottom_k/.top_k/.between/.index/.encode/.explain/ .quantile_partition_sort, string/bytes/spatial method forms (.strings, .bytes, .morton_argsort, .hilbert_argsort), and on an index: OrderIndex.ordered/.select/.median/.minimum/.maximum/.top_k/ .bottom_k/.between/.unique/.runs/.inverse_permutation/ .storage_bytes, plus the derived-snapshot builders .merged_with(delta) (stable O(N+D) merge of new rows — extracts keys only for the delta, so it beats a rebuild ~10x on payloads with Python key extraction) and .refresh(payload) (O(N) revalidation of the retained permutation with the full stability rule, falling back to a rebuild). Codecs: AutoOrderCodec (default), MortonOrderCodec, HilbertOrderCodec, or any OrderCodec subclass.

Use

import numpy as np
from monotonic_order import Order

training = np.random.default_rng(1).normal(size=1_000_000)
with Order.fit(training, n_bins=256) as order:
    print(order.model.storage_bytes, order.model.median, order.rank(0.0))
    ordered = order.sort(np.random.default_rng(2).normal(size=1_000_000))

Build an exact reusable index when several order-statistic queries target the same payload snapshot:

records = [{"name": "c", "score": 2},
           {"name": "a", "score": 1},
           {"name": "b", "score": 1}]

order = Order(key=lambda row: np.int64(row["score"]))
index = order.index(records)
print(index.minimum, index.median(), index.ordered())

Exact one-shot order statistics do not require a complete permutation for fixed-width keys:

middle = order.select(records, len(records)//2)
lower_median = order.median(records, method="lower")
minimum, maximum = order.minmax(records)
smallest = order.bottom_k(records, 100)
largest = order.top_k(records, 100)
print(order.last_plan)
# minmax: int64 -> native-fused-scalar-minmax (...)

select is stable for duplicate keys: it returns the same labelled payload that would occupy the requested rank after a complete stable ordering.

For duplicate-heavy reference distributions, repeated quantile knots become planner hints:

order = Order.fit(reference, fitted_atom_threshold=0.10)
middle = order.median(new_payload, key=lambda row: row.score)
print(order.last_plan.reference_hit, order.last_plan.fallback_used)

The fitted pivot is checked against new_payload. A miss caused by distribution drift falls back to universal exact radix selection.

Continuous float64 references use checked quantile ranges rather than atom pivots. Runtime adaptation is observable and resettable:

print(order.last_plan.drift_score, order.last_plan.drifted)
print(order.planner_stats)
order.reset_planner()

The engine exposes the compiled key representation and execution decision:

encoded = order.encode(np.array([3, 1, 2], dtype=np.int64))
plan = order.explain(np.array([3, 1, 2], dtype=np.int64))
print(plan)
# argsort: int64 -> native-lsd-u64 (exact, stable; N=3; words=1; ...)

After execution, order.last_plan records the path that actually ran. Custom semantic domains can subclass OrderCodec and return explicit EncodedKeys. Order.reserve(N) can preallocate the grow-only native workspace; current capacity and growth counts are available through order.runtime.stats.

Order arbitrary payloads by one monotonic numeric key per item:

import numpy as np
from monotonic_order import Order

records = [{"name": "c", "score": 2},
           {"name": "a", "score": 1},
           {"name": "b", "score": 1}]

order = Order()
ordered = order.sort(records, key=lambda row: np.int64(row["score"]))
# a, b, c -- equal score=1 records remain stable

keys = np.array([30, -5, 10], dtype=np.int64)
permutation = order.argsort(keys)

Order.argsort supports exact uint64, int64, float64, NumPy datetime64/timedelta64, and UUID keys. Order.lexargsort composes multiple fields with per-field direction and missing-value policy.

Exact variable-length bytes and Unicode ordering are supported, with explicit normalization/casefold policy and integer-ranked Enum helpers. For data already stored as a concatenated byte blob plus offsets, use radix_bytes_argsort directly to avoid Python key-materialization overhead.

Explicit-bounds Morton 2D/3D and Hilbert 2D spatial-curve encoding are supported two ways: the standalone morton_encode/hilbert_encode (returning MortonEncoding/HilbertEncoding with quantized cells, clipping count and exact=False), or as codecs plugged directly into the engine:

from monotonic_order import Order, HilbertOrderCodec

order = Order(codec=HilbertOrderCodec(bounds=((0, 1), (0, 1)), bits=32))
permutation = order.argsort(points)
plan = order.explain(points)  # auditable: codec, kernel, exact=False

Hilbert improves consecutive-point locality over Morton, at a higher encoding cost — see ORDER_ENGINE_RESULTS.md section H for measured numbers.

Typing and lifecycle

MonotonicOrder ships PEP 561 inline type hints (py.typed) for every public module. Two conventions are intentional, not oversights:

• Fields like descending/nulls on OrderCodec.encode/Order.argsort are typed object rather than bool/str. A single call can carry either one scalar value or a per-field sequence for composite keys, so the precise type is validated at runtime (isinstance checks that raise TypeError/ValueError) rather than narrowed statically; narrowing the annotation would make composite calls a type error even though they are supported and tested.
• **options: object forwarding methods (Order.minimum/maximum, Order.strings/bytes/morton_*/hilbert_*) intentionally pass their keyword arguments straight through to the underlying function; the underlying function's own signature is the source of truth for what is accepted.

Object lifecycle:

• MonotonicOrder owns a native handle and must be released with .close() or a with MonotonicOrder(...) as model: block; __del__ frees it as a backstop, but backstop timing is not guaranteed, so do not rely on it for early release.
• Order owns an OrderRuntime (reusable native workspace) and, once warmed via Order.fit(...), a MonotonicOrder reference model. It is itself a context manager: with Order.fit(reference) as engine: closes the model and clears any workspace it created on exit. If runtime= was passed explicitly (a shared OrderRuntime), Order.close() never clears that shared runtime — only the runtime an Order created for itself.
• The default module-level monotonic_order.order instance is intentionally never closed by the library. Do not call .close() on it; construct your own Order()/Order.fit(...) when you need explicit lifecycle control.
• OrderRuntime, OrderIndex, EncodedKeys, OrderPlan, RunMetadata, ReferenceProfile, DriftReport, PlannerStats, and RuntimeStats hold only NumPy buffers and Python values (no native handles); they need no explicit release and are safe to let the garbage collector reclaim.

See THEORY.md §12.2 for the companion data-ownership/mutation contract (what is copied vs. referenced).

Serialization

pickle support follows the same live-handle-vs-value-object split as lifecycle:

• MonotonicOrder, Order, OrderRuntime, and OrderIndex explicitly refuse pickling (TypeError) because each references live process state (a native handle, a native workspace, or an object that references one of those). This is a deliberate safety decision, not a missing feature: MonotonicOrder's default pickling used to "succeed" by serializing its raw ctypes pointer value, producing a clone that aliased the same native allocation — closing both objects then double-frees it, which reliably crashes the interpreter. Reconstruct these in the target process instead (MonotonicOrder(data, n_bins), Order(...)/Order.fit(...), engine.index(payload, ...)).
• EncodedKeys, OrderPlan, RunMetadata, ReferenceProfile, DriftReport, PlannerStats, and RuntimeStats are plain frozen dataclasses over NumPy arrays and Python scalars, with no process-specific state; they pickle and unpickle normally, so telemetry, a fitted reference's quantile knots, or an index's run metadata can be persisted or sent across a process boundary independently of the live objects that produced them.

Wheels

make wheel builds a single abi3 wheel (monotonic_order-*-cp39-abi3-<platform>.whl) covering every CPython 3.9+ interpreter on the host platform/architecture — this has been built and smoke-tested for Linux x86_64 in this repository's development environment. .github/workflows/wheels.yml runs cibuildwheel across Linux (x86_64), macOS (x86_64 + arm64), and Windows (AMD64) on tag pushes or manual dispatch, building and smoke-testing one wheel per platform the same way, plus an sdist; those platforms need GitHub's hosted runners to actually execute and have not been built or run outside CI.

Native development build

cd MonotonicOrder
make
make test
make test-properties  # property/fuzz suite; needs pip install ".[test]"
make asan              # standalone C API under ASAN/UBSAN
make asan-python        # the actual Python extension under ASAN/UBSAN
make benchmark-engine

For reproducible parallel performance, set OMP_NUM_THREADS=3, OMP_PROC_BIND=close, and OMP_PLACES=cores in the process environment. make benchmark-engine does this automatically. Tune these values for a different CPU topology.

Memory

• Persistent model: sizeof(model) + 8*(K+1) bytes, about 2 KiB for K=256.
• Exact out-of-place sort: one output and one reusable workspace, 16*N bytes.
• Bounded-integer fast path may additionally use at most 512 KiB of counts.
• Construction: temporary 8*N bytes, released before the constructor returns.
• OrderIndex: retains keys plus a stable permutation, O(N); see ORDER_ENGINE_RESULTS.md section G for measured bytes and break-even query counts.

Measured results for the current machine are recorded in ORDER_ENGINE_RESULTS.md.