`nx_sort.nx` source

1// nx_sort.nx -- sorting algorithms.
2//
3// Canonical: this is the substrate-wide canonical sort library per
4// [[feedback-no-tool-proliferation-bit-level]].  Provides:
5//   - nx_sort_insertion: O(n^2) cache-friendly bubble-style;
6//     substrate canonical for small arrays.
7//   - nx_sort_heap:      O(n log n) in-place; substrate canonical
8//     for larger arrays.
9//   - nx_sort_is_sorted: invariant check.
10// Other primitives needing a sort MUST `import "nx_sort.nx"` and
11// compose; re-implementing inline is refused per the cardinal.
12// For quicksort variants see nx_quicksort.nx (separate canonical).
13//
14//   - Insertion sort: O(n^2) but cache-friendly, good for small arrays.
15//   - Heap sort:      O(n log n), in-place, uses sketch_min_heap.
16//
17// Pure i64 ascending order.
18//
19// genealogy_id: williams_1964_heap_sort + insertion_sort_folklore
20// lineage_id:   in_place_comparison_sort
21
22// nx_safety_envelope:
23//   intended_use:       AUTO_APPLIED -- primitive-specific tuning queued
24//   sil_target:         SIL1
25//   evidence:           [bulk_applied_2026-05-16, see-file-comment-for-detail]
26//   verdict:            NOT_YET_EVALUATED
27
28import "syscalls.nx"
29import "sketch_min_heap.nx"
30
31// ===== Insertion sort ===================================================
32
33// Bubble-style adjacent-swap insertion sort.  Simpler than classic
34// insertion sort (no shift-and-place phase; just swap-down).  O(N^2)
35// worst case; cache-friendly + correct + no OOB reads.
36//
37// Fixed 2026-05-20: the prior implementation had a break-by-overrun
38// pattern (`if arr[j] <= key { j = -1 }`) that read arr[j] after j
39// had already been decremented to -1 -- undefined-behavior OOB read.
40// Substrate-honesty audit caught it when nx_bench_core consolidated
41// to compose this primitive (per the bit-level no-tool-proliferation
42// cardinal); prior version had zero KAT coverage (only nx_sort_heap
43// was tested), so the bug slipped past every smoke.  Reclamation
44// directed INWARD: fix the canonical + add KAT.
45func nx_sort_insertion(arr: *i64, n: i64) -> i64 {
46    var i: i64 = 1
47    while i < n {
48        var j: i64 = i
49        while j > 0 {
50            if arr[j] < arr[j - 1] {
51                let tmp: i64 = arr[j]
52                arr[j] = arr[j - 1]
53                arr[j - 1] = tmp
54            }
55            j = j - 1
56        }
57        i = i + 1
58    }
59    return 0
60}
61
62// ===== Heap sort (via sketch_min_heap) =================================
63//
64// Push all elements onto the heap, then pop in order to produce
65// ascending output.  O(n log n) time, O(n) extra memory for heap.
66
67func nx_sort_heap(arr: *i64, n: i64) -> i64 {
68    if n <= 1 { return 0 }
69    let h: *MinHeap = nx_heap_alloc(n + 8)
70    var i: i64 = 0
71    while i < n {
72        nx_heap_push(h, arr[i], i)
73        i = i + 1
74    }
75    var k: i64 = 0
76    while k < n {
77        arr[k] = nx_heap_peek_key(h)
78        nx_heap_pop(h)
79        k = k + 1
80    }
81    return 0
82}
83
84// ===== Sorted-check =====================================================
85//
86// Returns 1 if arr is non-decreasing, 0 otherwise.
87
88func nx_sort_is_sorted(arr: *i64, n: i64) -> i64 {
89    var i: i64 = 1
90    while i < n {
91        if arr[i] < arr[i - 1] { return 0 }
92        i = i + 1
93    }
94    return 1
95}
nx_sort.nx source

`nx_sort.nx` source
