Merge sort (Lisp)

From LiteratePrograms
Jump to: navigation, search
Other implementations: ACL2 | C | C++ | dc | Erlang | Haskell | Java | JavaScript | Lisp | Oz | Perl | 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.

[edit] 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 checks whether a given list contains zero element or one element. If a given list is small, the merge-sort function just output the list without sorting.

<<mergesort.lisp>>=
(defun small (list)
  (or (eq (length list) 0) (eq (length list) 1)))

The right-half function returns the right half of a given list. The left-half function returns the remaining left half of a given list.

<<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 #'<))

[edit] 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
hijacker
hijacker
hijacker
hijacker