std.sort是 Zerolang 标准库中专用于"调用者自有存储"（caller-owned storage）的排序模块，提供从插入排序、稳定/不稳定排序到旋转、分区、去重、第 n 小值选择与有序归并的整套原地算法。本文以 docs/articles/modules/sort.md 为主线，结合 std/sort.0 的源码实现与 conformance/native/pass/std-search-sort-widths.0 的合规测试，完整梳理全部 63 个可运行 API、逐算法讲解底层实现，并给出可直接复制的组合示例，帮助你按需挑选正确的排序原语。

何时使用std.sort

在 Zerolang 中，凡是需要对由调用方自己持有的可变存储（MutSpan<i32>、MutSpan<u32>、MutSpan<usize>，以及底层为这些类型的定长数组）进行原地排序，或需要使用标量排序辅助操作（交换、旋转、判序、分区、去重、选择、归并）时，都应该使用std.sort。

它遵循 Zerolang 标准库的"写进调用者存储、不静默分配"设计原则（见 docs/articles/standard-library.md）：所有函数都是Void/Bool/usize返回的纯原地操作，不分配内存、不持有隐藏状态、不搬移自有（owned）值。当前可运行表面刻意保持"小而类型化"——只覆盖i32、u32、usize三种标量宽度，并在每个宽度上提供升序/降序两个方向。

从 skill-data/stdlib.md 中记录的完整可调用表面（### std.sort一节，第 1519–1585 行）可以看到，每个 API 都带有显式类型签名，例如insertionI32(arg0: MutSpan<i32>) -> Void、swapI32(arg0: MutSpan<i32>, arg1: usize, arg2: usize) -> Bool、mergeSortedI32(arg0: MutSpan<i32>, arg1: Span<i32>, arg2: Span<i32>) -> usize。Agent 可以通过zero skills get stdlib在安装的编译器上直接查询这一表面。

API 总览：63 个可运行函数

下面的分组表格完整收录 docs/articles/modules/sort.md 中列出的全部 API（每类操作均覆盖i32/u32/usize三种宽度）。返回类型中，Void表示纯原地改写；Bool表示"是否成功/是否成立"；usize表示返回拆分位置、唯一前缀长度或写入计数。

排序：插入 / 稳定 / 不稳定（升序 + 降序）

重排：反转 / 交换 / 旋转

判序谓词

分区：划分 + 分区校验

去重：有序存储原地紧凑

选择：第 n 小 / 第 n 大

归并：有序输入合并到调用者存储

源码级解读：每个算法在std/sort.0里如何实现

Zerolang 的标准库是图背书（graph-backed）的：编译器实际使用的是二进制std/sort.graph存储，而同目录下的 std/sort.0 是供人类审阅的可读投影（参见 docs/articles/standard-library.md）。由于.0投影的每个函数都对应真实可调用面，我们可以从它精确还原算法行为。以下解读以i32版本为例，u32、usize版本逻辑完全一致。

插入排序与"稳定"的真实含义

__zero_std_sort_insertion_i32（std/sort.0 第 1–13 行）从下标 1 开始，把每个元素向前插入到已排序前缀的合适位置，插入时逐位右移更大元素。而stable系列（第 15–17 行）直接委托给插入排序：

fn __zero_std_sort_stable_i32(items: MutSpan<i32>) -> Void { __zero_std_sort_insertion_i32(items) }

这符合排序稳定性的一般结论：插入排序是稳定的，因为它只越过严格大于当前值的元素，不会打乱相等元素的相对顺序。降序版本insertion_desc（第 104–116 行）把比较方向反转为"越过严格小于当前值的元素"。

不稳定排序是选择排序

__zero_std_sort_unstable_i32（第 19–37 行）是典型的选择排序：每轮在未排序后缀中扫描出最小值best，若与当前位置不同则交换。选择排序通过交换完成排列，相等元素可能被交换错位，因此被标注为"不稳定"。降序版本unstable_desc（第 122–140 行）同样只是把items[scan] < items[best]反转成>。

反转、交换与旋转：基础重排原语

• reverse_i32（第 39–51 行）使用左右双指针原地对调，直到两指针相遇；
• swap_i32（第 53–61 行）先做越界检查：left或right任一>= len时直接返回false，这是文档中"索引非法返回false"契约的实现来源；
• rotate_left_i32（第 63–80 行）先计算shift = amount % len，随后逐位把首元素搬到尾部，重复shift次；空存储直接返回；
• rotate_right_i32（第 82–91 行）没有独立的右旋循环，而是复用左旋：rotateLeft(len - shift)，从源码可以推断这是通过"右旋 k 位等价于左旋 len-k 位"实现的。这也解释了为什么测试里rotateRightI32(rotate_i32, 2_usize)在左旋 7 位之后仍能回到[1, 2, 3, 4, 5]。

判序：一趟线性扫描

is_sorted_i32（第 93–102 行）与is_sorted_desc_i32（第 142–151 行）都只做一趟线性扫描：一旦发现相邻元素违反目标方向立即返回false，否则返回true。空数组与单元素数组天然满足"已排序"，这也是后续去重、归并断言可依赖它们的原因。

分区：一趟交换 + 拆分索引

partition_i32（第 153–166 行）维护一个write指针：扫描过程中凡是< pivot的元素都与items[write]交换并前进write，结束时write即"小于 pivot 的值的数量"，也是拆分索引。降序版partition_desc（第 184–197 行）把条件换成> pivot。与之配套的is_partitioned_i32（第 168–182 行）用seen_tail标记"已经进入尾部"，一旦在尾部再次看到< pivot的元素就返回false。

有序去重：原地紧凑 + 唯一前缀长度

dedupe_sorted_i32（第 215–229 行）假设输入已排序，用快慢指针write/index把每个"首次出现的值"搬到前缀，返回的write就是唯一前缀长度；数组剩余槽位的旧值不会被清理（这正是"原地紧凑"的含义）。

第 n 小选择：有界选择排序

select_nth_i32（第 231–254 行）先检查nth >= len，越界返回false；否则只对0..=nth区间执行选择排序的"找最小值并交换"步骤，结束后items[nth]恰为第 n 小的值，而无需把整个数组排完。降序版（第 256–279 行）同样反转比较方向。

有序归并：三循环写入 + 容量封顶

merge_sorted_i32（第 281–307 行）在dst容量、left、right三者都未耗尽时，取两路中较小者写入；随后两个尾随循环分别拷贝剩余左路、剩余右路。每次写入前都以written < capacity兜底，因此当dst容量不足以容纳全部输入时，函数只写满容量并返回实际写入数——调用方应像文档示例那样保证dst容量不小于left + right的总长。降序版（第 309–335 行）把比较改为>=以保证合并结果稳定有序。

综合示例：一票式验证全部能力

下面的示例直接取自 docs/articles/modules/sort.md 的 Example 小节，它把排序、去重、反转、交换、左右旋转、降序分区、降序判序、稳定/不稳定降序、第 n 小选择、有序归并全部串起来，并在末尾用一条if断言组合验证所有结果：

pub fn main(world: World) -> Void raises { var values: [5]i32 = [5, 1, 4, 2, 3] std.sort.stableI32(values) let unique_len: usize = std.sort.dedupeSortedI32(values) std.sort.unstableI32(values) std.sort.reverseI32(values) let swapped: Bool = std.sort.swapI32(values, 0_usize, 4_usize) std.sort.rotateLeftI32(values, 2_usize) std.sort.rotateRightI32(values, 2_usize) let high_len: usize = std.sort.partitionDescI32(values, 2) let high_partitioned: Bool = std.sort.isPartitionedDescI32(values, 2) std.sort.stableDescI32(values) std.sort.unstableDescI32(values) var selected: [5]i32 = [9, 1, 4, 7, 2] let selected_ok: Bool = std.sort.selectNthI32(selected, 2_usize) let left_sorted: [2]i32 = [1, 3] let right_sorted: [3]i32 = [2, 4, 5] var merged: [5]i32 = [0, 0, 0, 0, 0] let merged_len: usize = std.sort.mergeSortedI32(merged, left_sorted, right_sorted) if std.sort.isSortedDescI32(values) && swapped && unique_len == 5 && high_len == 3 && high_partitioned && selected_ok && selected[2] == 4 && merged_len == 5 && values[0] == 5 && values[4] == 1 { check world.out.write("sort ok\n") } }

逐行推演要点：

• stableI32后values == [1,2,3,4,5]，dedupeSortedI32因无重复返回唯一前缀长度5；
• unstableI32重排后reverseI32得到[5,4,3,2,1]，swapI32(values, 0, 4)交换后得到[1,4,3,2,5]，返回true；
• rotateLeftI32(values, 2)与rotateRightI32(values, 2)前后相消，回到[1,4,3,2,5]；
• partitionDescI32(values, 2)把大于 2 的4、3、5移向前，返回3，且isPartitionedDescI32为true；
• stableDescI32/unstableDescI32最终使values呈降序，因此末尾values[0] == 5 && values[4] == 1；
• selectNthI32(selected, 2)使selected[2] == 4（第三小的值）；
• mergeSortedI32(merged, [1,3], [2,4,5])写入 5 个值，merged_len == 5。

值得注意的是，示例中的stableI32/unstableI32在本例中结果相同，但在含有重复键的实际场景中，"稳定"意味着相等元素的相对顺序被保留，而选择排序式的unstable会通过交换破坏该顺序——这是选择 API 时需要牢记的差异。

行为契约：Effects、Allocation、Error、Ownership 与 Target

原文档在示例之后给出了五项显式契约，全部与源码实现一一对应：

• Effects：只写入调用方提供的可变存储（MutSpan<T>），无其他副作用；
• Allocation behavior：零分配。所有操作都在既有存储内完成，std/sort.0中的实现仅使用局部变量与就地交换，没有任何分配器调用；
• Error behavior：整体为"无错误"表面，但两个Bool返回 API 是例外且可安全探测：swap在索引越界时返回false，selectNth在nth >= len时返回false（对应源码第 53–61 行与第 231–254 行的显式边界检查）；
• Ownership：排序助手是"类型化标量助手"，不移动 owned 值，即不会搬移或销毁调用者的所有权语义；
• Target support：覆盖当前编译器目标（见 docs/articles/target-capabilities.md），纯内存操作不依赖宿主能力。

与std.search、std.collections的配合：排序是流水线的一环

std.sort在 Zerolang 标准库中的定位不是孤立模块，而是与 docs/articles/modules/search.md（有序二分/边界查找）、docs/articles/modules/collections.md（固定容量集合）协作：

• 排序 + 二分查找：先std.sort.stableI32(values)，再用std.search.binaryI32(values, needle)、lowerBoundI32/upperBoundI32、countSortedI32等完成有序数据上的查找。降序数据则对应binaryDescI32/lowerBoundDescI32/upperBoundDescI32（std/search.0中按同一宽度矩阵实现）。skill-data/stdlib.md 第 201–234 行给出了这条标准流水线：排序后用expect std.search.binaryI32(values, 4) == 3等断言验证；
• 排序 + 去重 + 集合语义：dedupeSortedI32返回的唯一前缀长度可直接作为后续std.collections固定容量操作的"有效长度"使用；
• 归并 + 外部归并思路：mergeSortedI32的"写入计数"契约使其天然适合在调用者缓冲上实现自底向上的归并流程，配合std.mem.prefix/std.mem.dropPrefix切分输入（见下面测试用例）。

测试验证：conformance 中的宽度矩阵与边界用例

std.sort的契约由 conformance 测试直接锁定。最完整的是 conformance/native/pass/std-search-sort-widths.0，它覆盖了所有宽度组合的关键断言：

• 边界失败路径：swapI32(swap_i32, 0_usize, 3_usize)对 3 元素数组返回false（第 138 行）；selectNthI32(select_i32, 9_usize)对 5 元素数组返回false（第 166 行）；
• 旋转取模：rotateLeftI32(rotate_i32, 7_usize)与rotateRightI32(rotate_i32, 2_usize)组合后回到原序（第 146–147 行），验证了amount % len的语义；
• 去重长度：[1,1,2,4,4,5]去重后返回4，唯一前缀为1,2,4,5（第 67–68、184 行）；
• 分区与判序：partitionI32返回拆分索引且isPartitionedI32为true，partitionDesc在降序方向上同理（第 49–66 行）；
• 稳定/不稳定结果：升序、降序两组均验证isSorted且首尾元素符合预期（第 187–190 行）；
• 归并 + 容量：mergeSortedI32把std.mem.prefix(i32s, 3)与std.mem.dropPrefix(i32s, 3)两段合并回 6 元素缓冲，断言写入数 5 且前缀有序（第 167–168、195 行）。

此外，conformance/native/pass/std-collections-algorithms.0 展示了std.sort与std.collections组合使用的场景：对values[..len]做insertionI32后，用isSortedI32(live)校验有序性，再配合count/contains完成集合类断言。

设计取舍：为什么现在没有"泛型比较器排序"

原文档明确指出一个设计立场：当前的排序表面刻意保持小而类型化，泛型比较器排序应等待更强的比较器契约（comparator contracts），而不是把无类型回调约定偷偷塞进标准库。

从源码结构看，这一决策带来的直接好处是：

1. 零分配与零运行时开销：每个函数都是针对具体标量宽度的直接内联实现，不经过函数指针或回调间接层；
2. 可编译期校验：MutSpan<i32>等签名让越界写入、类型不匹配在构建期即被拦截，错误行为全部显式化（Bool返回 + 边界检查）；
3. 便于 Agent 理解与调用：如 skill-data/stdlib.md 所展示，zero skills get stdlib输出的每个签名都是自描述的；没有回调约定就没有隐式契约，修复和推理成本更低。

代价则是：当你需要对结构体、字符串等非标量类型排序时，std.sort目前不直接提供入口，需要自行实现比较逻辑或等特性比较器契约成熟后由标准库补充。这与 Zerolang "以图（graph）为程序语义、强调显式与可推理"的整体语言设计一致（参见 docs/articles/language-reference.md）。

小结

std.sort是 Zerolang 标准库中面向标量存储的最小完备排序面：63 个 API 覆盖三种宽度 × 升序/降序 × 排序/重排/判序/分区/去重/选择/归并七类操作，全部原地、零分配、无隐藏错误，边界行为（越界交换、越界选择、容量封顶归并）通过Bool/usize返回值显式暴露。结合 std/sort.0 的直白实现与 conformance/native/pass/std-search-sort-widths.0 的断言矩阵，你可以放心地把排序、去重、第 n 小选择与归并流水线建立在std.sort之上，并与std.search、std.collections无缝衔接。