# Merge sort (Lisp)

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
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]>
```