Insertion sort

Insertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. \nIt is much less efficient than the more advanced algorithms such as Quicksort, Heapsort, or Merge sort, but its advantages are:

• Simple to implement\n* Efficient on (quite) small data sets\n* Efficient on data sets which are already substantially sorted\n* Stable (ie, does not change the order of already ordered elements)\n* Does not suffer from poor "worst case input" performance\n* Minimal memory requirements

In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input.\nThe choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm. Sorting is typically done in-place. The result array after k iterations contains the first k entries of the input array and is sorted. \nIn each step, the first remaining entry of the input is removed, inserted into the result at the right position, thus extending the result: becomes: with each element > x copied to the right as it is compared against x. The algorithm can be described as:

1. Start with the result being the first element of the input.\n# Loop over the input array until it is empty, "removing" the first remaining (leftmost) element.\n# Compare the removed element against the current result, starting from the highest (rightmost) element, and working left towards the lowest element.\n# If the removed input element is lower than the current result element, copy that value into the following element to make room for the new element below, and repeat with the next lowest result element.\n# Otherwise, the new element is in the correct location; save it in the cell left by copying the last examined result up, and start again from (2) with the next input element.

A simple Python implementation of this follows:

def insertsort(array):\n     for removed_index in range(1, len(array)):\n         removed_value = array[removed_index]\n         insert_index = removed_index\n         while insert_index > 0 and array[insert_index - 1] > removed_value:\n             array[insert_index] = array[insert_index - 1]\n             insert_index = insert_index - 1\n         array[insert_index] = removed_value

One coding using a functional programming language such as Haskell might be:\n

\n  insert :: Ord a => a -> [a] -> [a]\n  insert item []  = [item]\n  insert item (h:t) | item <= h = item:h:t\n                    | otherwise = h:(insert item t)
 insertsort :: Ord a => [a] -> [a]\n  insertsort []    = []   \n  insertsort (h:t) = insert h (insertsort t)\n

Insertion sort is very similar to bubble sort.\nIn 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. \nSo 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.\nIt takes O(n²) time in the average and worst cases, which makes it impractical for sorting large numbers of elements.\nHowever, 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. If comparisons are very costly compared to swaps, then using binary insertion sort can be a good strategy. Binary insertion sort employs binary search to find the right place to insert new elements, and therefore performs log(n!) comparisons which is even less than Merge sort for finite n, though both do O(n log n) comparisons. The algorithm as a whole still takes O(n²) time on average due to the series of swaps required for each insertion, and since it always uses binary search, the best case is no longer O(n) but O(n log n). D.L. Shell made substantial improvements to the algorithm, and the modified version is called Shell sort. \nIt compares elements separated by a distance that decreases on each pass. Shellsort has distinctly improved running times in practical work and is often a good choice. \nIn contrast, C A R Hoare's Quicksort works by recursively dividing the array to be sorted into smaller runs each of which is sorted separately; highly optimized implementations of Quicksort often use insertion sort to sort these runs once they get "small enough". \nHeapsort is another high speed sort algorithm, which is more practical than any variant of insertion sort for most real world work as it has almost constant running time regardless of input ordering, can be written to take little additional memory space, and is worst case not too much slower than Quicksort.

External links

\n*Insertion sort animated\n* Another animated Java applet showing a step-by-step insertion sort. \n \n Category:Sort algorithms