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