Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Insertion sort
open-in-new
<p>Insertion sort is a simple <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting algorithm</a> that builds the final <a href="/facts/Sorted_array/VAuF76AG">sorted array</a> (or list) one item at a time <a href="/facts/Comparison_sort/X1PvE50c">by comparisons</a>. It is much less efficient on large lists than more advanced algorithms such as <a href="/facts/Quicksort/1BeqhLAH">quicksort</a>, <a href="/facts/Heapsort/Cz22lLKq">heapsort</a>, or <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a>. However, insertion sort provides several advantages: </p> <ul><li>Simple implementation: <a href="/facts/Jon_Bentley_(computer_scientist)/WEK7bgSs">Jon Bentley</a> shows a version that is three lines in <a href="/facts/C_(programming_language)/Ky2No763">C</a>-like pseudo-code, and five lines when <a href="/facts/Program_optimization/nXz6RpRM">optimized</a>.</li> <li>Efficient for (quite) small data sets, much like other quadratic (i.e., <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>n</i>2)) sorting algorithms</li> <li>More efficient in practice than most other simple quadratic algorithms such as <a href="/facts/Selection_sort/uIsGffcr">selection sort</a> or <a href="/facts/Bubble_sort/Go9JnLk2">bubble sort</a></li> <li><a href="/facts/Adaptive_sort/8BPWrNSD">Adaptive</a>, i.e., efficient for data sets that are already substantially sorted: the <a href="/facts/Time_complexity/77T62gmf">time complexity</a> is <a href="/facts/Big_O_notation/weFFjSWg">O</a>(<i>kn</i>) when each element in the input is no more than k places away from its sorted position</li> <li><a href="/facts/Stable_sort/PwHpj1Gs">Stable</a>; i.e., does not change the relative order of elements with equal keys</li> <li><a href="/facts/In-place_algorithm/Ghe2PJUF">In-place</a>; i.e., only requires a constant amount O(1) of additional memory space</li> <li><a href="/facts/Online_algorithm/64TsU7Yz">Online</a>; i.e., can sort a list as it receives it</li></ul> <p>When people manually sort cards in a <a href="/facts/Contract_bridge/ohDtVpd9">bridge</a> hand, most use a method that is similar to insertion sort. </p>