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