Insertion sort is a simple sort algorithm where the result is built up one entry at a time. It is much less efficient than the more advanced algorithms such as Quicksort or Mergesort but advantages are:
Sorting is done in-place. The result array after k iterations contains the first k entries of the input array and is sorted. In each step, the first remaining entry of the input is removed, inserted into the result at the right position, thus extending the result:
becomes:+------ result ------+------ input ------+ | <= x | > x | x | ... | +--------------------+-------------------+
with each element > x copied to the right as it is compared against x.+-------- result --------+---- input ----+ | <= x | x | > x | ... | +------------------------+---------------+
The algorithm can be described as:
def straightinsertionsort(array):for removed_index in range(1, len(array)): removed_value = array[removed_index] insert_index = removed_index while insert_index > 0 and array[insert_index - 1] > removed_value: array[insert_index] = array[insert_index - 1] insert_index = insert_index - 1 array[insert_index] = removed_value
One coding using a functional programming language such as Haskell might be:
> insert :: Ord a => a -> [a] -> [a] > insert item [] = [item] > insert item (h:t) | item <= h = item:h:t > | otherwise = h:(insert item t)> insertsort :: Ord a => [a] -> [a] > insertsort [] = [] > insertsort (h:t) = insert h (insertsort t)
Insertion sort is very similar to bubble sort. In bubble sort, after k passes through the array, the k largest elements have bubbled to the top. (Or the k smallest elements have bubbled to the bottom, depending on which way you do it.) In insertion sort, after k passes through the array, you have a run of k sorted elements at the bottom of the array. Each pass inserts another element into the sorted run. So with bubble sort, each pass takes less time than the previous one, but with insertion sort, each pass may take more time than the previous one.
In the best case of an already sorted array, this implementation of insertion sort takes O(n) time: in each iteration, the first remaining element of the input is only compared with the last element of the result. It takes O(n2) time in the average and worst cases, which makes it impractical for sorting large numbers of elements. However, insertion sort's inner loop is very fast, which often makes it one of the fastest algorithms for sorting small numbers of elements, typically less than 10 or so.
D.L. Shell made an improvement to the algorithm, called Shellsort, that compares elements separated by a distance that decreases on each pass. Quicksort works by dividing the array to be sorted into smaller runs to be sorted separately; highly optimized implementations of Quicksort often use insertion sort to sort these runs once they get small enough.