目标：在不使用内置函数的情况下以函数方式对序列进行排序sorted(..)。
def my_sorted(seq):
"""returns an iterator"""
pass
动机：在 FP 方式中，我受到限制：
seq（可以是迭代器或已实现的列表）问题 1由于我不能 mutate seq，我需要维护一个单独的可变数据结构来存储排序后的序列。与 in-place 相比，这似乎很浪费list.sort()。其他函数式编程语言如何处理这个问题？
问题 2如果我返回一个可变序列，在功能范式中可以吗？
适当的防御性编程有时会很浪费，但您也无能为力。
这就是为什么从一开始就支持功能使用的语言对其本机不可变类型使用结构共享的原因；使用不是为它构建的语言（例如 Python）以函数式风格进行编程当然不会得到很好的支持。也就是说，排序操作不一定是结构共享的良好候选者（如果需要进行的不仅仅是微小的更改）。
因此，即使在其他函数式语言中，通常也会在排序中涉及至少一个复制操作。例如，Clojure 在临时可变数组上委托 Java 的本机（高度优化）排序操作，并返回包装该数组的 seq（从而使结果与用于填充相同的输入一样不可变）。如果输入是不可变的，而输出是不可变的，并且两者之间发生的事情对外部世界（尤其是任何其他线程）不可见，那么瞬态可变性通常是必要且适当的事情。
当然，排序不能完全惰性（输入的最后一个元素可能是输出的第一个元素），但您可以实现计算惰性排序，在读取整个序列后，仅根据请求逐个元素生成精确排序的输出。您还可以延迟读取输入，直到请求至少一个输出，这样排序和忽略结果将不需要计算。
对于这种计算惰性的方法，我所知道的最佳候选者是堆排序算法（您只需预先进行堆构建步骤）。
仅当没有其他人引用数据时，就地突变才是安全的，并期望它与排序之前一样。因此，一般来说，为排序结果使用新结构并不是很浪费。仅当您以线性方式使用数据时，就地优化才是安全的。
因此，只需分配一个新结构，因为这更普遍有用。就地版本是一种特殊情况。
浪费什么？位？电？挂钟时间？如果您有足够的 CPU 和大量数据，并行合并排序可能是最快完成的，但可能会产生许多中间表示。
通常，并行化算法可能会导致与串行算法非常不同的优化策略。例如，由于阿姆达尔定律，在本地重新执行冗余工作以避免共享。这在串行上下文中可能被认为是“浪费的”，但会导致算法的可扩展性更高。
使用可以以创建新数据结构的方式执行的排序算法，例如堆排序或归并排序。