Insertion Sort Algorithm

Insertion Sort builds the sorted array one element at a time by inserting each element into its correct position.

What is Insertion Sort?

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It treats the left side of the array as sorted and inserts each new element into its correct position inside that sorted portion.

A common way to understand Insertion Sort is to imagine arranging playing cards in your hand. You pick up one card at a time and place it where it belongs among the cards you have already sorted.

Core Intuition

Insertion Sort divides the array into two parts: a sorted portion on the left and an unsorted portion on the right. Initially, the first element is considered sorted because a single element is always sorted.

Then, the algorithm takes the next element from the unsorted portion and compares it with elements in the sorted portion. Any larger elements are shifted one position to the right, creating space for the current element to be inserted in the correct place.

Insertion Sort Algorithm Steps

1. Start from the second element.
   The first element is already considered sorted.
2. Store the current element.
   This element is called the key because we need to insert it into the correct position.
3. Compare with previous elements.
   Move left through the sorted portion while elements are greater than the key.
4. Shift larger elements right.
   Each larger element moves one position to the right to make space.
5. Insert the key.
   Place the key into the empty position where it belongs.
6. Repeat until sorted.
   Continue until every element has been inserted into the sorted portion.

Interactive Insertion Sort Visualization

Use the controls below to see how Insertion Sort compares adjacent elements, swaps them, and gradually builds the sorted part of the array from right to left.

Dry Run Example

Suppose we want to sort:

[5, 2, 4, 6, 1, 3]

Iteration 1: Insert 2

• Sorted portion: [5]
• Key = 2
• Since 5 > 2, shift 5 right.
• Insert 2 at index 0 → [2, 5, 4, 6, 1, 3]

Iteration 2: Insert 4

• Sorted portion: [2, 5]
• Key = 4
• Since 5 > 4, shift 5 right.
• 2 is not greater than 4, so insert 4 after 2 → [2, 4, 5, 6, 1, 3]

Iteration 3: Insert 6

• Sorted portion: [2, 4, 5]
• Key = 6
• No element is greater than 6, so no shifting is needed.
• Array remains → [2, 4, 5, 6, 1, 3]

Iteration 4: Insert 1

• Sorted portion: [2, 4, 5, 6]
• Key = 1
• Shift 6, 5, 4, and 2 one position right.
• Insert 1 at the beginning → [1, 2, 4, 5, 6, 3]

Iteration 5: Insert 3

• Sorted portion: [1, 2, 4, 5, 6]
• Key = 3
• Shift 6, 5, and 4 right.
• Insert 3 after 2 → [1, 2, 3, 4, 5, 6]

The array is now sorted.

Insertion Sort Code in Python

This implementation sorts the array in place by shifting larger elements to the right and inserting the current key into its correct position.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # Shift elements greater than key one position to the right.
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert key into its correct position.
        arr[j + 1] = key

    return arr


print(insertion_sort([5, 2, 4, 6, 1, 3]))

Time and Space Complexity

When Should You Use Insertion Sort?

Interview Notes and Common Pitfalls

This section highlights the key concepts interviewers expect you to understand, along with common mistakes that can lead to bugs during implementation.

What interviewers may expect you to know

• Insertion Sort builds a sorted portion from left to right.
• The current element is stored as a key before shifting begins.
• Larger elements are shifted right instead of repeatedly swapped.
• It is stable because equal elements are not moved ahead of each other.
• It is in-place because it uses O(1) extra space.
• Its best case is O(n) when the array is already sorted.
• Its average and worst-case time complexity is O(n²).

Common mistakes

• Forgetting to store arr[i] in a key variable before shifting.
• Using the wrong condition in the while loop.
• Placing the key at arr[j] instead of arr[j + 1].
• Accidentally making the algorithm unstable by shifting equal elements unnecessarily.
• Claiming the best-case time complexity is O(n²), even though it is O(n) for an already sorted array.
• accessing nums[j + 1] out of bounds.
• Forgetting that the last i elements are already sorted after i passes.
• Claiming the best case is O(n²) even when using the early-stop optimization.
• Using Bubble Sort when a faster sorting algorithm is required.

Related coding interview problems

• Sort an Array
• Insertion Sort List
• Sort List
• Merge Sorted Array
• Squares of a Sorted Array

Quick Quiz

Key Takeaways

• Insertion Sort builds the sorted array one element at a time.
• It works by taking a key and inserting it into the correct position in the sorted portion.
• It is stable and sorts in place.
• Its best-case time complexity is O(n) for already sorted arrays.
• Its average and worst-case time complexity is O(n²).
• It is most useful for small or nearly sorted datasets, not large random arrays.