合併排序

Merge Sort 是一種常見的排序演算法，平均案例複雜度為 O(n log n)，最差情況複雜度為 O(n log n)。雖然它不能就地執行，但它保證了所有情況下的複雜性。

Merge Sort 反覆將輸入拆分為兩個，直到達到空列表或單個元素列表。到達分割樹的底部後，它會再次向上執行，將兩個已排序的分割合併到一起，直到剩下單個排序列表。

使用此方法，Merge Sort 的 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)))))))