Editing Insertion sort (section)

{{Short description|Sorting algorithm}}
{{Infobox algorithm
|class=[[Sorting algorithm]]
|image=Insertion sort.gif
|image size=300px
|caption=Insertion sort animation
|data=[[Array data structure|Array]]
|time=<math>O(n^2)</math> comparisons and swaps
|best-time=<math>O(n)</math> comparisons, <math>O(1)</math> swaps
|average-time=<math>O(n^2)</math> comparisons and swaps
|space=<math>O(n)</math> total, <math>O(1)</math> auxiliary
|optimal=No
}}

'''Insertion sort''' is a simple [[sorting algorithm]] that builds the final [[sorted array]] (or list) one item at a time [[Comparison sort|by comparisons]]. It is much less efficient on large lists than more advanced algorithms such as [[quicksort]], [[heapsort]], or [[merge sort]]. However, insertion sort provides several advantages:

* Simple implementation: [[Jon Bentley (computer scientist)|Jon Bentley]] shows a version that is three lines in [[C (programming language)|C]]-like pseudo-code, and five lines when [[Program optimization|optimized]].<ref name="pearls"/>
* Efficient for (quite) small data sets, much like other quadratic (i.e., [[big O notation|O]](''n''<sup>2</sup>)) sorting algorithms
* More efficient in practice than most other simple quadratic algorithms such as [[selection sort]] or [[bubble sort]] 
* [[Adaptive sort|Adaptive]], i.e., efficient for data sets that are already substantially sorted: the [[time complexity]] is [[big O notation|O]](''kn'') when each element in the input is no more than {{mvar|k}} places away from its sorted position
* [[Stable sort|Stable]]; i.e., does not change the relative order of elements with equal keys
* [[In-place algorithm|In-place]]; i.e., only requires a constant amount O(1) of additional memory space
* [[Online algorithm|Online]]; i.e., can sort a list as it receives it

When people manually sort cards in a [[Contract bridge|bridge]] hand, most use a method that is similar to insertion sort.<ref>{{cite book |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist) |year=1983 |title=Algorithms |publisher=Addison-Wesley |isbn=978-0-201-06672-2 |page=95 |url=https://archive.org/details/algorithms00sedg/page/95 |url-access=registration}}</ref>