Insertion sort in Common Lisp

Question

This is my first bit of significant code in Common Lisp, an implementation of insertion sort. Being new to Lisp in general, I'm wondering if this code follows best Lisp practices in regards to program design.

;;; Return a portion of a list
(defun slice (elements from-index to-index)
 (cond
 ((= from-index to-index) nil)
 (t (cons (nth from-index elements) (slice elements (+ from-index 1) to-index)))))
;;; Return a list omitting a portion
(defun splice (elements from-index to-index)
 (append (slice elements 0 from-index) (slice elements to-index (length elements))))
;;; Move element in list to new index, return new list
(defun move (elements from-index to-index)
 (let ((spliced (splice elements from-index (+ from-index 1))))
 (append (slice spliced 0 to-index) (list (nth from-index elements)) (slice spliced to-index (length spliced)))))
;;; Find the determined (via predicate) correct index for an element in a list
(defun find-ordered-index (elements predicate index &optional (key index))
 (cond
 ((or (= index 0) (= key 0)) 0)
 ((funcall predicate (nth (- key 1) elements) (nth index elements)) (find-ordered-index elements predicate index (- key 1)))
 (t key)))
;;; Return sorted list
(defun insertion-sort (elements predicate &optional (index 0))
 (cond
 ((= index (length elements)) elements)
 (t (insertion-sort (move elements index (find-ordered-index elements predicate index)) predicate (+ index 1)))))

Answer 1

Trivial

Use 1- instead of (- ... 1).

Avoid very long lines (Emacs will indent for you).

Do not use cond when a single if without progn would do.

Memory

Use nconc instead of append when possible to avoid unnecessary consing (in your case, splice allocates a fresh list, so its result can be passed to nconc).

Catastrophic

Whenever you use nth, you are using the wrong algorithm.

Optimal sort is linearithmic: O(n*log(n)).

Insert sort is quadratic: O(n^2).

Your implementation is O(n^3):

1. nth is O(n)
2. slice is O(n^2) (calls nth * recursion).
3. splice and move are also O(n^2) (call slice).
4. find-ordered-index is O(n).
5. insertion-sort is O(n^3) (calls move * recursion).

• Jabari King: In places where recursing (like in slice) were quadratic, would iteration using the loop macro be better?
• sds: recursion and iteration are algorithmically equivalent.
• Jabari King: Well, slice is implemented using linear recursion, so it is called n times itself. If I were to implement slice using iteration, wouldn't the list only be traversed once?
• sds: whenever you call nth you are traversing the list.
• Jabari King: So if instead of accumulating values by accessing them with nth, using a loop and collecting values from from-index to to-index should take one order of n less time for the whole slice function

Answer 2

If you're interested in using what the language provides...

..you don't have to implement slice yourself, look at SUBSEQ.

..for find-ordered-index you could use POSITION-IF

Answer 3

You were trying to implement the algorithm as it is described for collections with certain properties, which, as noted by sds led you to create a very inefficient implementation, since the property that accessing an element anywhere in collection takes constant time simply doesn't hold for lists.

Now, a more interesting question to ask would be: is it in principle possible to implement insertion sort for lists? And, the answer here is: "it depends". If you take the definition of insertion sort from Cormen's book or similar literally, then there is no way, because constant element access time is a requirement and by its nature list doesn't satisfy that requirement. However, if you relax that requirement and only satisfy some other properties of the algorithm, then there may be a solution!

Some properties of the algorithm that may be satisfied together:

1. The sorting is in place, only constant (and small) amount of extra memory needs to be allocated.
2. At any given time there is a sorted and unsorted part of the collection.
3. There is a helper insert function which, given an element and a sorted portion of the collection will insert the element into that collection such that the order established by the comparison function is not violated.
4. The running time is the same.
5. The behavior exhibited by completely sorted and reversed inputs are the same.

I'm not going to prove the claim about running time, but, informally, you can see why this would be true: insert would either perform constant time operation by prepending an element to the list, or by appending it to the list. Or, it will look through the entire list to find the correct position to insert the element. Now, we look at each element of the list exactly once, and apply insert to it exactly once, thus, in the worst case, we will do N * N comparisons, (where N is the number of elements in the list).

---

Below is a possible implementation:

(defpackage :doodles (:use :cl :iterate))
(in-package :doodles)
(defun insert (list elt cmp previous-tail)
 (when (funcall cmp (car elt) (car list))
 (setf (cdr elt) list
 list elt)
 (return-from insert (values list previous-tail)))
 (when (funcall cmp (car elt) (car previous-tail))
 (iter
 (for tail :on (cdr list))
 (for prev :on list)
 (when (funcall cmp (car elt) (car tail))
 (setf (cdr prev) elt
 (cdr elt) tail)
 (return-from insert (values list previous-tail)))))
 (setf (cdr previous-tail) elt
 previous-tail elt)
 (values list previous-tail))
(defun insertion-sort (list cmp)
 (let ((sorted list)
 (unsorted (cdr list)))
 (setf (cdr sorted) nil)
 (iter
 (with sorted-tail := sorted)
 (for unsorted-head :on unsorted)
 (multiple-value-bind (head tail)
 (insert sorted unsorted-head cmp sorted-tail)
 (setf sorted head
 sorted-tail tail))
 (finally
 (progn
 (setf (cdr sorted-tail) nil)
 (return sorted))))))