## Description

Insertion sort is an in place algorithm that orders a list of elements.

## Performance

Best Average Worst
$O(n)$ $O(n^2)$ $O(n^2)$

6 10 8 5 1 7

6 10 8 5 1 7

6 8 10 5 1 7

5 6 8 10 1 7

1 5 6 8 10 7

1 5 6 7 8 10

## LISP implementation

;Stephen Rudolph
;1/12/09
;Insertion-Sort

;;Return a list without the nth item in l
(defun remove-nth(n l)
(if (> (- n 1) (length l))
l
(if (= n 0)
(cdr l)
(cons (car l) (remove-nth (- n 1) (cdr l))))))

;;Return a list with x inserted after the nth element in l
(defun insert-after-nth(x n l)
(if (>= n (length l))
(append l (list x))
(if (= n -1)
(cons x l)
(cons (car l) (insert-after-nth x (- n 1) (cdr l))))))

;;Loop through all indices (match-index) less than key-index and sort the element at key-index
(defun insertion-sort-body(l key-index match-index)
(if (= match-index -1)
(cons (nth key-index l) (remove-nth key-index l))
(if (< (nth key-index l) (nth match-index l))
(insertion-sort-body l key-index (- match-index 1))
(insert-after-nth (nth key-index l) match-index (remove-nth key-index l)))))

;;Sort the first key-index items in l
(defun insertion-sort-loop(l key-index)
(if (= key-index (length l))
l
(insertion-sort-loop (insertion-sort-body l key-index (- key-index 1)) (+ key-index 1))))

;;Sort list l with the insertion sort algorithm
(defun insertion-sort(l)
(insertion-sort-loop l 1))

## Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood