Insertion Sort Explained Step by Step With Code

Insertion sort is the way you already sort playing cards in your hand. You pick up one card at a time and slide it into the right place among the cards you are holding.

Most tutorials call it just another slow sort. That is a mistake. Insertion sort is the one simple sort that real code actually uses, and I will show you why.

What is insertion sort?

Insertion sort puts a list in order by growing a sorted section one item at a time. It treats the first item as a sorted list of one. Then it takes the next item and inserts it into the right spot in that sorted section.

To insert an item, it slides the bigger sorted items one step to the right to make room. It keeps doing this for every item until the whole list is sorted. The sorted part on the left grows, and the unsorted part on the right shrinks.

It is one of the three simple sorts, next to selection sort and bubble sort. But it has one trick the other two do not.

How does insertion sort work step by step?

Reading the rule is not enough. You have to watch the slides happen. So let’s sort the list [5, 2, 4, 1] by hand, one item at a time.

Start with 5 as the sorted section. Take the next item, 2. It is smaller than 5, so slide 5 right and put 2 in front. The list is now [2, 5, 4, 1], with [2, 5] sorted.

Take 4. It is smaller than 5, so slide 5 right. It is bigger than 2, so stop and drop 4 in between. The list is now [2, 4, 5, 1], with [2, 4, 5] sorted. Take the last item, 1. It is smaller than everything, so slide 5, then 4, then 2 to the right, and place 1 at the front.

The result is [1, 2, 4, 5], fully sorted. Notice the key move. You never compare far away items. You only slide the sorted ones until the new item fits.

Insertion sort code in Python and C++

The code uses one loop for each new item and an inner loop that slides bigger items right. Here it is in Python.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]      # slide the bigger item right
            j -= 1
        arr[j + 1] = key             # drop the key into its spot
    return arr

The key is the item being placed. The inner loop slides every bigger item right, then the key drops into the gap. Here is the same logic in C++, the language most Indian placement tests expect.

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Both versions do the same thing. Hold one item as the key, slide the bigger sorted items right, then place the key in the gap that opens up.

What is the time complexity of insertion sort?

Insertion sort is O(n squared) in the worst case, when the list is in reverse order. Every new item then has to slide past all the ones before it. For 1,000 reversed items, that is close to half a million slides.

But here is its trick. On a list that is already sorted or nearly sorted, it runs in O(n), because each item barely moves. That best case is far better than bubble sort or selection sort manage in practice. The space is O(1), since it sorts in place, and it is stable. You can read the formal details on Wikipedia’s insertion sort page. The full picture lives in the post on time complexity.

When should you use insertion sort?

Reach for insertion sort when the list is small or already close to sorted. In both cases it is quick, simple to write and hard to get wrong. It also works well when data arrives one item at a time, since it can slot each new value straight into the sorted part.

The reason to skip it is large random data, where that O(n squared) cost shows up and slows everything down. For big lists, faster sorts like quick sort and merge sort win, though many of them still fall back to insertion sort for their smallest pieces.

FAQ

What is the time complexity of insertion sort?

O(n squared) in the worst and average cases. But the best case is O(n) on a sorted or nearly sorted list, which is its main strength. The space is O(1).

Is insertion sort faster than bubble sort?

Usually yes. Both are O(n squared), but insertion sort does fewer moves in practice and has a strong O(n) best case. That is why it gets used in real code and bubble sort does not.

Is insertion sort stable?

Yes. It never moves an equal item past another equal item, so items with the same value keep their original order. That property is called stability.

When is insertion sort the best choice?

On small lists or nearly sorted lists, and when data arrives one piece at a time. In those cases it is fast, simple and reliable.

Why do fast sorts use insertion sort inside them?

Because on tiny lists, insertion sort beats the fancy sorts thanks to its low overhead. So sorts like quicksort switch to it once the pieces they are working on get small.

What is the difference between insertion sort and selection sort?

Insertion sort slides each new item into a growing sorted section. Selection sort scans for the smallest item and places it. Insertion sort is usually faster on nearly sorted data.

So what should you remember?

Insertion sort grows a sorted list one item at a time, sliding each new value into place like cards in your hand. It is simple, stable and quick on small or nearly sorted data.

Do not write it off as just another slow sort. Its O(n) best case and low overhead make it the one simple sort that real software still reaches for. Learn it well and you will see it hiding inside the big algorithms.

Now try it yourself. Using insertion sort on the list [3, 1, 2], how many slides happen before the list is fully sorted?