方案 |本机排序功能复杂性
SCHEME | native sort function complexity
我正在四处寻找答案，但找不到任何答案，甚至在 SCHEME 手册中也找不到...
我想知道在方案（在基本包中）中实现的 native 排序函数的运行时复杂度是多少。
我听说过它是 O(n log n) 或 O(n2) 的谣言，但未确认为 100% 真实。
我也想听听那里使用的排序算法是什么。
谢谢！
leppie 的回答基本上是一个完整的回答。
简答：这取决于实现，但 R6RS 要求这种排序是稳定的，因此它很可能是合并排序。
您使用的是什么方案？
GNU MIT 方案
GNU MIT 方案implements two sort algorithms:
merge-sortquick-sort
正确实施每个将 运行 在 O(n log n) 时间内。这是任何比较排序算法的最佳时间。 sort 过程是 merge-sort 的别名。同样，它的可变对象 sort! 是可变对象 merge-sort!.
的别名
那么为什么有 quick-sort 呢？ quick-sort的好处是在允许变异的情况下可以原地进行排序。 quick-sort! 可以实现不需要任何额外的内存超出为输入向量分配的内存：它可以实现需要 exactly n space，而不是 O(n) space。这在当今的台式计算机上不是什么大问题，但在资源有限的情况下很重要。
C.A。 Hoare orginal paper 描述了快速排序。
球拍
根据 source, #lang racket uses a "Fast mergesort implementation based on half-copying merge algorithm”，Cezary Juszczak 着。
我正在四处寻找答案，但找不到任何答案，甚至在 SCHEME 手册中也找不到... 我想知道在方案（在基本包中）中实现的 native 排序函数的运行时复杂度是多少。 我听说过它是 O(n log n) 或 O(n2) 的谣言，但未确认为 100% 真实。
我也想听听那里使用的排序算法是什么。
谢谢！
leppie 的回答基本上是一个完整的回答。
简答：这取决于实现，但 R6RS 要求这种排序是稳定的，因此它很可能是合并排序。
您使用的是什么方案？
GNU MIT 方案
GNU MIT 方案implements two sort algorithms:
merge-sortquick-sort
正确实施每个将 运行 在 O(n log n) 时间内。这是任何比较排序算法的最佳时间。 sort 过程是 merge-sort 的别名。同样，它的可变对象 sort! 是可变对象 merge-sort!.
那么为什么有 quick-sort 呢？ quick-sort的好处是在允许变异的情况下可以原地进行排序。 quick-sort! 可以实现不需要任何额外的内存超出为输入向量分配的内存：它可以实现需要 exactly n space，而不是 O(n) space。这在当今的台式计算机上不是什么大问题，但在资源有限的情况下很重要。
C.A。 Hoare orginal paper 描述了快速排序。
球拍
根据 source, #lang racket uses a "Fast mergesort implementation based on half-copying merge algorithm”，Cezary Juszczak 着。