nx_quicksort.nx
buildroot/runtime/nx_quicksort.nx
about
nx_quicksort.nx -- Hoare quicksort (in-place, last-element pivot).
Canonical: this is the substrate-wide canonical quicksort per
[[feedback-no-tool-proliferation-bit-level]]. Other primitives
needing quicksort MUST `import "nx_quicksort.nx"` and compose;
re-implementing inline is refused per the cardinal. nx_qsort.nx +
nx_quickselect.nx may carry distinct semantics (selection vs sort)
but MUST declare "Distinct from [[nx_quicksort.nx]] because: ..."
in their headers.
genealogy_id: hoare_1961_quicksort
lineage_id: in_place_comparison_sort
references: Hoare 'Quicksort' CACM 4(7):321, 1961.
Sedgewick 1978 implementation analysis.
license: public_domain
complexity: avg O(n log n), worst O(n^2).
Tier discipline (no bare i64 in API surface):
- elements: *nx_int (swappable via nx_tier.nx)
- indices: nx_idx (platform-pointer-width)
- status: nx_int (small value; not platform-mandated i64)
The only place `i64` appears in NishiLang source is the entrypoint
main() return, where the kernel exit syscall ABI mandates 64-bit.
dependencies 2 imports · 2 importers
imports: nx_syscalls.nxnx_tier.nx
imported by: nx_quicksort_test.nxnx_triangulation_sort_string_graph.nx
structs
| none |
consts
| none |
functions
| 34 | func nx_quicksort_partition(arr: *nx_int, lo: nx_idx, hi: nx_idx) -> nx_idx called by 1: nx_quicksort_recur |
| 53 | func nx_quicksort_recur(arr: *nx_int, lo: nx_idx, hi: nx_idx) -> nx_int |
| 63 | func nx_quicksort(arr: *nx_int, n: nx_idx) -> nx_int |