Insertion sort in Common Lisp
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))
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