# Insertion sort

## Sorting algorithm / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Insertion sort?

Summarize this article for a 10 years old

SHOW ALL QUESTIONS

**Insertion sort** is a simple sorting algorithm that builds the final sorted array (or list) one item at a time 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 shows a three-line C/C++ version that is five lines when optimized.[1]
- Efficient for (quite) small data sets, much like other quadratic (i.e., O(
*n*^{2})) sorting algorithms - More efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort
- Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(
*kn*) when each element in the input is no more than k places away from its sorted position - Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it

Sorting algorithm

**Quick facts: Class, Data structure, Worst-case performance...**▼

Class | Sorting algorithm |
---|---|

Data structure | Array |

Worst-case performance | $O(n^{2})$ comparisons and swaps |

Best-case performance | $O(n)$ comparisons, $O(1)$ swaps |

Average performance | $O(n^{2})$ comparisons and swaps |

Worst-case space complexity | $O(n)$ total, $O(1)$ auxiliary |

When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.[2]