Merge sort (Scheme)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

This is an implementation of the merge sort algorithm in Scheme, as applied to cons-based lists. The sorting predicate is user-specified; use <= to provide the usual stable sorting of numbers.

There are three functions in the implementation. The first, split, is used to chop the list into two pieces, each of which we will later sort recursively:

<<split>>=
(define (split ls)
  (letrec ([split-h (lambda (ls ls1 ls2)
                      (cond
                        [(or (null? ls) (null? (cdr ls)))
                         (cons (reverse ls2) ls1)]
                        [else (split-h (cddr ls)
                                (cdr ls1) (cons (car ls1) ls2))]))])
    (split-h ls ls '())))

A more intuitive way of splitting the list might be to put all odd-positioned elements in one sublist, and the rest in another. This, however, is not stable: a list that is already partially-ordered according to the predicate might be rearranged.

For example, given a binary predicate string-length<= that returns #t iff the first argument is not longer than the second, and the list ("aaa" "bbb" "ccc"), you get ("aaa" "ccc" "bbb") back. Thus the trick of having a copy of the list that is consumed two elements at a time, in order to split the list in the middle.

The next, merge, is the heart of the algorithm and operates by interleaving the elements of two ordered lists in such a way that the combined list is ordered. This process takes only linear (O(n)) time:

<<merge>>=
(define (merge pred ls1 ls2)
  (cond
    [(null? ls1) ls2]
    [(null? ls2) ls1]
    [(pred (car ls1) (car ls2))
     (cons (car ls1) (merge pred (cdr ls1) ls2))]
    [else (cons (car ls2) (merge pred ls1 (cdr ls2)))]))

Finally, we use these together to implement mergesort, by splitting the list into two pieces, sorting them recursively, and then merging them. We handle the trivial cases by simply returning the list:

<<mergesort.scm>>=
split
merge
(define (merge-sort pred ls)
  (cond
    [(null? ls) ls]
    [(null? (cdr ls)) ls]
    [else (let ([splits (split ls)])
            (merge pred
              (merge-sort pred (car splits))
              (merge-sort pred (cdr splits))))]))

Download code