**Insertion sort** is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. 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
- Efficient for (quite) small data sets
- Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(
*n*+*d*), where*d*is the number of inversions - More efficient in practice than most other simple quadratic (i.e., O(
*n*2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(*n*) - 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

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.

Read more about Insertion Sort: Algorithm, Best, Worst, and Average Cases, Comparisons To Other Sorting Algorithms, Variants

### Famous quotes containing the word sort:

“... and the next summer she died in childbirth.

That’s all. Of course, there may be some *sort* of sequel but it is not known to me. In such cases instead of getting bogged down in guesswork, I repeat the words of the merry king in my favorite fairy tale: Which arrow flies for ever? The arrow that has hit its mark.”

—Vladimir Nabokov (1899–1977)