Insertion Sort

In Turkish: eklemeli sıralama
Pronunciation: in-SUR-shun SORT

Updated October 3, 20262 min read

In short

Insertion sort builds a sorted list one element at a time, putting each new one in its place among those already sorted, like sorting cards in your hand.

What is insertion sort?

The algorithm keeps the left part of the list sorted. It takes the next element, compares it with the sorted elements from right to left, shifts the larger ones one position to the right and drops the new element into the gap. Repeating this for every element produces a fully sorted list.

In the worst case, a list sorted in reverse, every element moves all the way left, giving O(n²) time. But when the input is already nearly sorted, each element moves only a little, and the running time approaches O(n). It sorts in place with O(1) extra memory, is stable, and can sort data as it arrives, one item at a time.

That efficiency on small and nearly sorted inputs makes insertion sort a building block of fast real-world sorts. Timsort, Python's sorting algorithm since 2002 and used by Java for sorting objects, uses insertion sort on short runs, and introsort implementations, used in many C++ standard libraries, switch to it for small partitions.

A common misconception is that every O(n²) sort is equally useless. Insertion sort has low overhead and excellent behavior on nearly sorted data, which is why it outperforms O(n log n) algorithms on small arrays of a few dozen elements and survives inside the best general-purpose sorts.

Key takeaways

Insertion sort inserts each element into place within a sorted prefix.
It is O(n²) in the worst case but close to O(n) on nearly sorted data.
It is in-place, stable and can sort items as they arrive.
Timsort and introsort use it for small pieces.
On small arrays it often beats O(n log n) algorithms.

Example

Insertion sort (Python)python

def insertion_sort(items):
    items = list(items)
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:   # shift larger elements right
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current                 # drop the element into the gap
    return items

print(insertion_sort([12, 11, 13, 5, 6]))   # [5, 6, 11, 12, 13]

Readers ask

When is insertion sort a good choice?

For small arrays, data that is already almost sorted, or items arriving one by one that must be kept in order. For large, random data, an O(n log n) algorithm is far faster.

Is insertion sort stable?

Yes. It only shifts elements that are strictly greater than the one being inserted, so equal elements keep their original relative order.

Why do fast sorting algorithms use insertion sort internally?

Because for small subarrays its simple loop and low overhead beat the bookkeeping of divide-and-conquer algorithms. Hybrid sorts like Timsort and introsort switch to it below a size threshold.