nx_sort.nx source
↩ module page · 102 lines · 3810 B
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}
96
97// Fixed two-word records sorted by first word. The second word remains attached.
98// Uses the same explicit index boundary as the canonical scalar insertion sort.
99func nx_sort_pairs_first(pairs:*i64,n:i64)->i64{
100 if n<0||n>9223372036854775807/16{return -1};if n==0{return 0};let p:i64=pairs as i64;if p<=0||n*16>9223372036854775807-p{return -1}
101 var i:i64=1;while i<n{var j:i64=i;while j>0{if pairs[j*2]<pairs[(j-1)*2]{let a:i64=pairs[j*2];let b:i64=pairs[j*2+1];pairs[j*2]=pairs[(j-1)*2];pairs[j*2+1]=pairs[(j-1)*2+1];pairs[(j-1)*2]=a;pairs[(j-1)*2+1]=b};j=j-1};i=i+1};return 0
102}