合并排序是一种常见的排序算法，平均情况复杂度为O(n log n)，最坏情况复杂度为O(n log n)。尽管它不能就地执行，但它保证O(n log n)了所有情况下的复杂性。
合并排序重复将输入分成两部分，直到到达空列表或单元素列表。到达拆分树的底部之后，它会往回备份，将两个已排序的拆分合并到一起，直到剩下一个已排序的列表。
使用此方法，合并排序的Scheme实现可能如下所示：
;; Merge two sorted lists into a single sorted list (define (merge list1 list2) (cond ((null? list1) list2) ((null? list2) list1) (else (let ((head1 (car list1)) (head2 (car list2))) ; Add the smaller element to the front of the merge list (if (<= head1 head2) (cons head1 ; Recursively merge (merge (cdr list1) list2)) (cons head2 ; Recursively merge (merge list1 (cdr list2)))))))) (define (split-list lst) (let ((half (quotient (length lst) 2))) ; Create a pair of the first and second halves of the list (cons (take lst half) (drop lst half)))) (define (merge-sort lst) (cond ((or (null? lst) ; empty list is sorted, so merge up (null? (cdr lst))) ; single-element list is sorted, so merge up lst) (else (let ((halves (split-list lst))) ; Recursively split until the bottom, then merge back up to sort (merge (merge-sort (car halves)) (merge-sort (cdr halves)))))))