Merge sort (Lisp)

From LiteratePrograms

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

This article explains how to implement merge sort in Lisp, especially in Common Lisp. For simplicity, we assume that every input element is a number.

Source code

<<mergesort.lisp>>=
(defun merge-sort (list)
  (if (small list) list
	  (merge-lists
		(merge-sort (left-half list))
		(merge-sort (right-half list)))))

The small function checks whether a given list contains zero element or one element. If a given list is smaller than two elements then there is no need to sort it, so the merge-sort function just outputs the list as it already is.

<<mergesort.lisp>>=
(defun small (list)
  (or (null list) (null (cdr list))))

The right-half function returns the right half of a given list. It does this by calculating how many elements the list has, and then extracting everything after the halfway element. The ceiling function ensures that the result of the division is a whole number. It does this by returning the whole number part of its argument thus losing any fractional part that might exist. This is necessary because the last function expects to receive a list and a whole number. The left-half function returns the remaining left half of a given list but it does so in an interesting way using the built-in function ldiff. This function returns a list consisting of elements which exist in the first argument but not in the second. Since we give it the list and the right-half of the list, it returns the difference which just happens to be the left-half of the list in this case.

<<mergesort.lisp>>=
(defun right-half (list)
  (last list (ceiling (/ (length list) 2))))
(defun left-half (list)
  (ldiff list (right-half list)))

The merge-lists function merge the elements in list1 and list2 in an increasing order. We use merge function provided by Common Lisp library.

<<mergesort.lisp>>=
(defun merge-lists (list1 list2)
  (merge 'list list1 list2 #'<))

Execution result

We executed the source code in Clisp under cygwin.

crypto@crypto ~/mergesort
$ clisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2006
[1]> (load "mergesort.lisp")
;; Loading file mergesort.lisp ...
;; Loaded file mergesort.lisp
T
[2]> (small '())
T
[3]> (small '(3))
T
[4]> (small '(1 200))
NIL
[5]> (left-half '(1 2 3 4 5 6 7 8 9 10 11))
(1 2 3 4 5)
[6]> (right-half '(1 2 3 4 5 6 7 8 9 10 11))
(6 7 8 9 10 11)
[7]> (merge-lists '(2 7 100 101) '(0 5 9 12 105))
(0 2 5 7 9 12 100 101 105)
[8]> (merge-sort '(3 4 8 0 6 7 4 2 1 9 4 5))
(0 1 2 3 4 4 4 5 6 7 8 9)
[9]>

Download code