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) $

Example

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

To all math majors: "Mathematics is a wonderfully rich subject."

Dr. Paul Garrett