Insertion sort

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 version that is three lines in C-like pseudo-code, and five lines when optimized.

Efficient for (quite) small data sets, much like other quadratic (i.
e.
, O(n2)) sorting algorithms May be more efficient in practice than most other simple quadratic algorithms such as selection sort or bubble sort – but relative incoming data order and read/write costs matter – with high exchange costs and randomly ordered data, selection sort is faster Adaptive, i.

Back to Algorithms →

Source: Wikipedia · Image: Wikimedia Commons · CC BY-SA 3.0