Insertion sort in Common Lisp

8 September 2013

Having an application where insertion sort would perform well (i.e. a mostly sorted list), I decided to implement it in Common Lisp. The result was only marginally better than SBCL’s built-in sort for a fully sorted list, and was worse for almost anything else. Still, the resulting function is the only non-recursive insertion sort in CL that I found and as such it actually does live up to its promise of performing well for mostly sorted lists.

(defun insertion-sort (list predicate &key (key #'identity))
  (let ((front list))
    (iter (for next = (cdr front))
          (for el = (car next))
          (while next)
          (if (funcall predicate
                       (funcall key el)
                       (funcall key (car front)))
              (progn
                (rplacd front (cdr next))
                (setf list (insert-sorted el list
                                          predicate :key key)))
              (setf front next)))
    list))

Where insert-sorted is (courtesy of lisptips.com):

(defun insert-sorted (object list predicate &key (key #'identity))
  (merge 'list (list object) list predicate :key key))

Moral of the story: Use sort.