scheme 合并排序
示例
合并排序是一种常见的排序算法，平均情况复杂度为O(nlogn)，最坏情况复杂度为O(nlogn)。尽管它不能就地执行，但它保证O(nlogn)了所有情况下的复杂性。
合并排序重复将输入分成两部分，直到到达空列表或单元素列表。到达拆分树的底部之后，它会往回备份，将两个已排序的拆分合并到一起，直到剩下一个已排序的列表。
使用此方法，合并排序的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)))))))