nx_mergesort.nx source
↩ module page · 87 lines · 2781 B
1// nx_mergesort.nx -- von-Neumann merge sort (top-down, stable).
2//
3// genealogy_id: von_neumann_1945_edvac
4// lineage_id: stable_comparison_sort
5// references: von Neumann 'First Draft of a Report on the EDVAC', 1945.
6// Knuth TAoCP Vol 3 5.2.4.
7// license: public_domain
8// complexity: O(n log n) time worst-case, O(n) extra space.
9
10// nx_safety_envelope:
11// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
12// sil_target: SIL1
13// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
14// verdict: NOT_YET_EVALUATED
15
16import "nx_syscalls.nx"
17import "nx_tier.nx"
18
19// Merge arr[lo..mid) and arr[mid..hi) using auxiliary buffer aux.
20// Both halves are already sorted; produce a stable merge back into arr.
21//
22// Uses a `took_left` guard flag because NishiLang doesn't have
23// `else if` -- the three cases (left exhausted / right exhausted /
24// both available) must be made mutually exclusive explicitly.
25func nx_mergesort_merge(arr: *nx_int, lo: nx_idx, mid: nx_idx, hi: nx_idx,
26 aux: *nx_int) -> nx_int {
27 var k: nx_idx = lo
28 while k < hi {
29 aux[k] = arr[k]
30 k = k + 1
31 }
32 var i: nx_idx = lo
33 var j: nx_idx = mid
34 var w: nx_idx = lo
35 while w < hi {
36 var took_left: nx_int = 0
37 // Case A: left exhausted -> take right.
38 if i >= mid {
39 arr[w] = aux[j]
40 j = j + 1
41 }
42 // Case B: left still has elements.
43 if i < mid {
44 // B1: right exhausted -> take left.
45 if j >= hi {
46 arr[w] = aux[i]
47 i = i + 1
48 took_left = 1
49 }
50 // B2: both available -> compare.
51 if j < hi {
52 if aux[i] <= aux[j] {
53 arr[w] = aux[i]
54 i = i + 1
55 took_left = 1
56 }
57 // B3: left's value > right's; took_left is 0 here.
58 if took_left == 0 {
59 arr[w] = aux[j]
60 j = j + 1
61 }
62 }
63 }
64 w = w + 1
65 }
66 return 0
67}
68
69func nx_mergesort_recur(arr: *nx_int, lo: nx_idx, hi: nx_idx, aux: *nx_int) -> nx_int {
70 if hi - lo > 1 {
71 let mid: nx_idx = lo + (hi - lo) / 2
72 nx_mergesort_recur(arr, lo, mid, aux)
73 nx_mergesort_recur(arr, mid, hi, aux)
74 nx_mergesort_merge(arr, lo, mid, hi, aux)
75 }
76 return 0
77}
78
79// Sort arr[0..n) stably in place using O(n) extra space.
80func nx_mergesort(arr: *nx_int, n: nx_idx) -> nx_int {
81 if n > 1 {
82 let aux_raw: *u8 = sys_mmap(n * 8)
83 let aux: *nx_int = aux_raw as *nx_int
84 nx_mergesort_recur(arr, 0, n, aux)
85 }
86 return 0
87}