(define (merge-sort lst (lt? <))
  (define (truthy=? a b)
    (eq? (not a) (not b)))

  (let sort ((lst lst)
             (size (length lst))
             (flip #f))
    (define (merge l r (res '()))
      (cond ((null? l) (append-reverse r res))
            ((null? r) (append-reverse l res))
            ((truthy=? (lt? (car r) (car l)) flip)
             (merge l (cdr r) (cons (car r) res)))
            (else
             (merge (cdr l) r (cons (car l) res)))))

    (if (<= size 1) lst
        (let*-values (((mid) (quotient size 2))
                      ((l r) (split-at lst mid)))
          (merge (sort l mid (not flip))
                 (sort r (- size mid) (not flip)))))))


经过球拍和Guile测试；需要SRFI 1和11。（如果要将它用于Guile，则需要调整用于可选参数的语法。）

此版本通过多种方式为Scheme量身定制：


列表的长度在开始时仅计算一次。在每个拆分中，拆分部分的长度将传递给每个递归调用。
合并步骤使用向右展开而不是向左展开，以进行尾递归。这样会在每个步骤中产生一个反向列表。
而不是在每次合并时都反向列表，我只是保留一个标志来说明列表是否反向。合并步骤会考虑此标志，然后进行正确的合并以维持排序稳定性。


评论

我在这里不确定协议的全部内容，但是您实际上是在问一个问题，还是只想进行一般性的批评？
@RobertHarvey我正在寻找对样式的一般性批评，以及寻求使代码更加高效的方法（从算法上来说，不是微优化方面）。实际上，我确实有此代码的更高性能版本，我将其发布为答案。不久。 :-)
由于您不愿意用lt？来调用问题，为什么不这样修改代码：（eq？（和（lt？（car r）（car l））#t）flip）
@MartinNeal主要是因为，如果我要去那里，我最好定义一个XNOR操作。我仍在考虑这样做。 :-)但是实际上，我认为我可以使您的想法适应而不是使用，因此，不是使用（和foo #t），而是使用（不是foo）（并且交换了分支）。进行编辑。
我最终创造了一个真理=？不使用。就像XNOR具有更易读的名称。 :-D

#1 楼

在致力于代码审查的站点上进行审查之前，经过四年，1400次查看和两次打票，这表明不可审查性是代码的显着特征。我认为，阻碍可审核性的是代码对任何阅读它的人的认知能力很高。

阅读


认知负荷始于最高层。合并排序是一个有据可查的算法。像许多对编程感兴趣的人一样，我为算法类​​编写了一个实现。它之所以能很好地完成任务，是因为细节是不平凡的（发现这些细节是20年前的一项艰巨的工作，当时以计算的Von-Neumann架构命名的John Von-Neumann就是这样……“有多严肃？”可能会问，答案将是“曼哈顿严重计划”）。我想我像其他人一样，已经忘记了实现过程的来龙去脉，并且回收了任何将突触存储伪代码的突触。对我来说，合并排序以某种\ $ \ mathcal {O}（n \ log n）\ $方式有点模糊，因为这是最可能与sorting抽象级别相关的事实。
出于这次审查的目的，我将说下一层是实施的最高层。这里的问题提出了一个巧妙的实现细节：只计算一次列表的长度。我不记得我的实现是如何计算长度的或者它是如何计算的……我想我使用的是向量/数组而不是列表[我用Clojure或Racket编写了它]。无论如何，聪明会使得代码难以审核。
在下一个层次上，结构会引起额外的认知负担。充其量，define和let/let*的混合形式不一致。最糟糕的是，let只是使可读性差的代码成为了嵌套define值得在Scheme本身中实现的那种。
最后，还有变量名。

建议


通过注释代码来帮助读者。不需要将合并排序方面的专业知识作为理解的先决条件。考虑使用诸如HtDP程序食谱之类的内容作为起点。解释算法并在实现中使用该解释的术语。
让我想起了Kernighan的杠杆：每个人都知道调试的难度是编写程序的两倍。因此，如果您在编写代码时尽可能聪明，那么将如何调试它？查看代码，实施创新的地方并不明显。即使获得了一定程度的合并排序知识，我仍然拥有侦探性的工作来理解创新。
使用define而不是let/let*使所有内容明确，语法更好，并且高级概念可以清楚地表达出来，而不是混入实现细节中，例如可以与merge，truthy=?等一起定义mid。
无需使用精简JavaScript的标准来命名参数/变量。 l和r可能是“左”和“右”的抽象，但是左和右不是代码中显式的抽象。

关于项目2的更多内容：如果要关注性能，那么为什么列表和参数传递而不是向量或其他数据结构似乎是一个问题相关的。更进一步，基准测试可能是增加复杂性的最佳理由：


程序员浪费大量时间来考虑或担心程序非关键部分的速度，而在考虑调试和维护时，这些提高效率的尝试实际上会产生严重的负面影响。我们应该忘记效率低下的问题，例如大约97％的时间：过早的优化是万恶之源。然而，我们不应该放弃那关键的3％的机会。


快速排序似乎是使用FFI进行有意义的改进的地方，可以有效地改进大小有趣的数据。