Proposal: sorting toolkit — sort_by / sort_desc_by / sort_with, stable & O(n log n), for records and queries #11

New issue

Closed

opened 2026-08-29 20:21:56 +02:00 by orkun · 1 comment

orkun commented

2026-08-29 20:21:56 +02:00

Owner

Summary

Grow sorting from the current single primitive into a small, game-friendly
sorting toolkit: sort by a key or comparator, sort records/entities
(not just numbers), ascending or descending, stable, and backed by an
efficient algorithm.

Current state

List.sort today is an in-place ascending insertion sort over numeric
elements only (selfhost/emit_list.ludic). That's O(n²) and can't sort a list
of structs by a field, which is what games usually need.

Why it matters for game devs

Leaderboards / high scores (by score, descending).
Draw order / z-sorting sprites by y or layer every frame.
Inventory / shop sorted by name, rarity, price.
AI: nearest-N targets by distance.

These are everyday tasks; today they force the developer to hand-roll a sort.

Proposed API (illustrative)

# doc-check: skip — illustrative API sketch
List.sort(scores)                              # keep: ascending numeric
List.sort_by(enemies, fn(e) -> e.pos.y)        # key selector -> sort by y (draw order)
List.sort_desc_by(players, fn(p) -> p.score)   # leaderboard
List.sort_with(items, fn(a, b) -> a.price - b.price)   # full comparator

sort_by (ascending by a key), sort_desc_by, sort_with (comparator).
Stable so equal keys keep their prior order (matters for tie-breaks).
Works on lists of records and on query results.

Considerations

Replace insertion sort with an efficient stable algorithm (merge sort or
a stable Tim/merge hybrid) for large lists; keep insertion sort as the small-n
fast path.
Determinism: identical inputs → identical order (no unstable quicksort pivots
tied to memory).
Native/C-free; must handle any element type, incl. property/record types.
Comparator/closure support may depend on the type-system work in #1.

Scope / acceptance

sort_by, sort_desc_by, sort_with in the self-host compiler.
Stable, O(n log n) algorithm; documented complexity.
Sort records and query results, not just scalars.
Docs updates + leaderboard / draw-order examples.
Tests incl. stability.

Related: #1 (closures/type system), #2 (List namespace).

## Summary Grow sorting from the current single primitive into a small, game-friendly sorting toolkit: **sort by a key or comparator**, sort **records/entities** (not just numbers), ascending **or** descending, **stable**, and backed by an efficient algorithm. ## Current state `List.sort` today is an **in-place ascending insertion sort over numeric elements only** (`selfhost/emit_list.ludic`). That's O(n²) and can't sort a list of structs by a field, which is what games usually need. ## Why it matters for game devs - **Leaderboards / high scores** (by score, descending). - **Draw order / z-sorting** sprites by `y` or layer every frame. - **Inventory / shop** sorted by name, rarity, price. - **AI**: nearest-N targets by distance. These are everyday tasks; today they force the developer to hand-roll a sort. ## Proposed API (illustrative) ```ludic # doc-check: skip — illustrative API sketch List.sort(scores) # keep: ascending numeric List.sort_by(enemies, fn(e) -> e.pos.y) # key selector -> sort by y (draw order) List.sort_desc_by(players, fn(p) -> p.score) # leaderboard List.sort_with(items, fn(a, b) -> a.price - b.price) # full comparator ``` - `sort_by` (ascending by a key), `sort_desc_by`, `sort_with` (comparator). - **Stable** so equal keys keep their prior order (matters for tie-breaks). - Works on lists of records and on query results. ## Considerations - Replace insertion sort with an efficient **stable** algorithm (merge sort or a stable Tim/merge hybrid) for large lists; keep insertion sort as the small-n fast path. - Determinism: identical inputs → identical order (no unstable quicksort pivots tied to memory). - Native/C-free; must handle any element type, incl. `property`/record types. - Comparator/closure support may depend on the type-system work in #1. ## Scope / acceptance - [ ] `sort_by`, `sort_desc_by`, `sort_with` in the self-host compiler. - [ ] Stable, O(n log n) algorithm; documented complexity. - [ ] Sort records and query results, not just scalars. - [ ] Docs updates + leaderboard / draw-order examples. - [ ] Tests incl. stability. Related: #1 (closures/type system), #2 (List namespace).

orkun added the

proposal

priority:high

area:stdlib

labels 2026-08-29 20:21:56 +02:00

orkun referenced this issue from a commit

2026-08-30 10:39:32 +02:00

feat(stdlib): sorting toolkit — sort_by/sort_desc_by/sort_with + stable merge sort (#11)

orkun commented

2026-08-30 10:40:14 +02:00

Author

Owner

Shipped in 4aa2012.

Sorting toolkit — grows List sorting from the numeric-only insertion sort into a small, game-friendly toolkit:

List.sort_by(s, keyfn) — ascending by a key (draw order, inventory by price)
List.sort_desc_by(s, keyfn) — descending (leaderboards)
List.sort_with(s, cmpfn) — full cmp(a, b) -> int comparator (multi-field sorts)

Comparators/keys are passed as named top-level functions rather than inline lambdas, so the toolkit ships now without waiting on closures (#1); when #1 lands, lambda selectors can be added on top with no API change.

Engine: a stable, bottom-up merge sort — O(n log n), O(n) scratch, deterministic. A single predicate decides stability ("take the right run's head only on a strict win"), so equal keys keep their prior order — the tie-break leaderboards and z-sorting need. List.sort is now a hybrid: insertion sort for small n (<32), merge sort above; both stable, so output is identical and existing golden renders are unchanged.

Sorts records and query results (record slices hold pointer elements, so the key/comparator receives the record). Key functions must return a numeric type (int/fixed/long).

Acceptance: sort_by/sort_desc_by/sort_with ✓ · stable O(n log n) ✓ · records & query results ✓ · docs + leaderboard/draw-order examples ✓ · tests incl. stability ✓. All suites green (28 self-host / 46 test / 29 test-tools); reseeded, C-free bootstrap fixpoint holds.

Shipped in 4aa2012. **Sorting toolkit** — grows List sorting from the numeric-only insertion sort into a small, game-friendly toolkit: - `List.sort_by(s, keyfn)` — ascending by a key (draw order, inventory by price) - `List.sort_desc_by(s, keyfn)` — descending (leaderboards) - `List.sort_with(s, cmpfn)` — full `cmp(a, b) -> int` comparator (multi-field sorts) Comparators/keys are passed as **named top-level functions** rather than inline lambdas, so the toolkit ships now without waiting on closures (#1); when #1 lands, lambda selectors can be added on top with no API change. **Engine:** a stable, bottom-up **merge sort** — O(n log n), O(n) scratch, deterministic. A single predicate decides stability ("take the right run's head only on a strict win"), so equal keys keep their prior order — the tie-break leaderboards and z-sorting need. `List.sort` is now a hybrid: insertion sort for small n (<32), merge sort above; both stable, so output is identical and existing golden renders are unchanged. Sorts records and query results (record slices hold pointer elements, so the key/comparator receives the record). Key functions must return a numeric type (int/fixed/long). **Acceptance:** sort_by/sort_desc_by/sort_with ✓ · stable O(n log n) ✓ · records & query results ✓ · docs + leaderboard/draw-order examples ✓ · tests incl. stability ✓. All suites green (28 self-host / 46 test / 29 test-tools); reseeded, C-free bootstrap fixpoint holds.

orkun closed this issue

2026-08-30 10:40:19 +02:00