Insertion Sort - Understanding with Visualization and Examples

Problem Statement❯

Given an array of integers, your task is to sort the array in non-decreasing order using the Insertion Sort algorithm.

Insertion Sort builds the final sorted array one element at a time. It is much like sorting playing cards in your hands — you take one card at a time and insert it into its correct position relative to the cards already sorted.

Your goal is to understand how Insertion Sort compares elements, shifts them, and places each item into its correct location during the sorting process.

Examples❯

Input Array	Sorted Output	Description
[5, 2, 4, 6, 1, 3]	[1, 2, 3, 4, 5, 6]	Typical unsorted array with mixed values
[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]	Already sorted array — best case
[5, 4, 3, 2, 1]	[1, 2, 3, 4, 5]	Reverse sorted array — worst case
[2, 2, 2, 2]	[2, 2, 2, 2]	All elements are the same — no shifting required
[7]	[7]	Single element — trivially sorted
[]	[]	Empty array — nothing to sort

Visualization Player

Solution❯

Understanding the Problem

We are given an array of numbers, and our goal is to sort them in increasing order using a simple technique called Insertion Sort.

Think of how you sort playing cards in your hand. You pick one card at a time and place it in the correct position among the cards you've already sorted. Insertion Sort works just like that — it builds the sorted array one element at a time.

Step-by-Step Solution

We start from the second element (index 1) and compare it with elements before it. If it's smaller than the previous one, we shift the previous one to the right. We keep doing this until we find the right spot for the current element.

We repeat this for every element until the entire array is sorted.

Let’s take an example: `[5, 2, 4, 6, 1, 3]`

Start with 2. Compare with 5. Since 2 < 5, shift 5 to the right and place 2 in the first position.
Now the array becomes: [2, 5, 4, 6, 1, 3]
Next, take 4. Compare with 5. Since 4 < 5, shift 5 and place 4. Now: [2, 4, 5, 6, 1, 3]
Next is 6. It's greater than 5, so it stays in place.
Take 1. It’s smaller than all previous, so shift them all and place 1 at the front: [1, 2, 4, 5, 6, 3]
Finally, place 3 in its correct spot: [1, 2, 3, 4, 5, 6]

Step by step, we moved each item to its correct position. That’s the core idea!

Edge Cases and Their Intuition

1. Already Sorted Input

Example: [1, 2, 3, 4]
Here, each new element is already in the right position, so no shifting is needed. We only compare. This is the best-case scenario, and it runs very quickly — in linear time.

2. Reverse Sorted Input

Example: [5, 4, 3, 2, 1]
Now, every element must be moved all the way to the front. This takes the most effort — maximum number of comparisons and shifts. This is the worst-case scenario with quadratic time complexity.

3. All Elements Are the Same

Example: [2, 2, 2, 2]
Each element equals the previous one, so no shifting happens. But comparisons are still made. The array remains unchanged, and this case performs better than the worst case.

4. Single Element or Empty Array

Example: [7] or []
These are trivially sorted. The algorithm recognizes this immediately and does nothing. These are special cases and are handled naturally without any extra code.

Finally

Insertion Sort is simple, intuitive, and efficient for small arrays or nearly sorted data. While not optimal for large datasets, it's a great starting point for understanding how sorting works step by step.

Algorithm Steps❯

Start from the second element (index 1) of the array.
Set the current element as the key.
Compare the key with the elements before it.
Shift all elements that are greater than the key one position to the right.
Insert the key into its correct position.
Repeat the process for all elements until the array is sorted.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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]
            j -= 1
        arr[j + 1] = key
    return arr

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    insertion_sort(arr)
    print("Sorted array is:", arr)

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	In the best case (when the array is already sorted), each element is compared only once with its predecessor and no shifting is needed. This results in a linear number of operations.
Average Case	O(n^2)	On average, each element is compared with about half of the previously sorted elements, resulting in a quadratic number of comparisons and shifts as the array size increases.
Worst Case	O(n^2)	In the worst case (when the array is reverse sorted), each element is compared and shifted against all previous elements, leading to the maximum number of operations — roughly n*(n-1)/2 — which is O(n^2).

Space Complexity❯

O(1)

Explanation: Insertion sort is an in-place algorithm. It requires only a constant amount of extra space for the key and index variables, regardless of the input size.

Detailed Step by Step Example❯

Let us take the following array and apply the Insertion Sort algorithm to sort the array in ascending order.

{ "array": [6,3,8,2,7,4], "showIndices": true, "specialIndices": [] }

Pass 1

Element at index=1 is the key.

{ "array": ["key : ",3], "showIndices": false, "specialIndices": [], "emptyIndices": [0] }

Our Goal: Take element 3 at index=1 and insert it into the sorted portion of array.

{ "array": [6,3,8,2,7,4], "showIndices": true, "highlightIndices": [1], "highlightIndicesGreen": [0], "specialIndices": [], "labels": { "1": "key" } }

Shift all elements greater than the key 3, on the left side of the key, one position to the right.

➜ 6 at index=0 is greater than key 3. Move it to right by one position.

{ "array": [6,6,8,2,7,4], "showIndices": true, "highlightIndices": [0, 1], "highlightIndicesGreen": [0,1], "specialIndices": [], "emptyCompIndices": [0] }

Insert key 3 into the correct position index=0.

{ "array": [3,6,8,2,7,4], "showIndices": true, "highlightIndicesGreen": [0,1], "specialIndices": [] }

Pass 2

Element at index=2 is the key.

{ "array": ["key : ",8], "showIndices": false, "specialIndices": [], "emptyIndices": [0] }

Our Goal: Take element 8 at index=2 and insert it into the sorted portion of array.

{ "array": [3,6,8,2,7,4], "showIndices": true, "highlightIndices": [2], "highlightIndicesGreen": [0,1], "specialIndices": [], "labels": { "2": "key" } }

Shift all elements greater than the key 8, on the left side of the key, one position to the right.

Insert key 8 into the correct position index=2.

{ "array": [3,6,8,2,7,4], "showIndices": true, "highlightIndicesGreen": [0,1,2], "specialIndices": [] }

Pass 3

Element at index=3 is the key.

{ "array": ["key : ",2], "showIndices": false, "specialIndices": [], "emptyIndices": [0] }

Our Goal: Take element 2 at index=3 and insert it into the sorted portion of array.

{ "array": [3,6,8,2,7,4], "showIndices": true, "highlightIndices": [3], "highlightIndicesGreen": [0,1,2], "specialIndices": [], "labels": { "3": "key" } }

Shift all elements greater than the key 2, on the left side of the key, one position to the right.

➜ 8 at index=2 is greater than key 2. Move it to right by one position.

{ "array": [3,6,8,8,7,4], "showIndices": true, "highlightIndices": [2, 3], "highlightIndicesGreen": [0,1,2,3], "specialIndices": [], "emptyCompIndices": [2] }

➜ 6 at index=1 is greater than key 2. Move it to right by one position.

{ "array": [3,6,6,8,7,4], "showIndices": true, "highlightIndices": [1, 2], "highlightIndicesGreen": [0,1,2,3], "specialIndices": [], "emptyCompIndices": [1] }

➜ 3 at index=0 is greater than key 2. Move it to right by one position.

{ "array": [3,3,6,8,7,4], "showIndices": true, "highlightIndices": [0, 1], "highlightIndicesGreen": [0,1,2,3], "specialIndices": [], "emptyCompIndices": [0] }

Insert key 2 into the correct position index=0.

{ "array": [2,3,6,8,7,4], "showIndices": true, "highlightIndicesGreen": [0,1,2,3], "specialIndices": [] }

Pass 4

Element at index=4 is the key.

{ "array": ["key : ",7], "showIndices": false, "specialIndices": [], "emptyIndices": [0] }

Our Goal: Take element 7 at index=4 and insert it into the sorted portion of array.

{ "array": [2,3,6,8,7,4], "showIndices": true, "highlightIndices": [4], "highlightIndicesGreen": [0,1,2,3], "specialIndices": [], "labels": { "4": "key" } }

Shift all elements greater than the key 7, on the left side of the key, one position to the right.

➜ 8 at index=3 is greater than key 7. Move it to right by one position.

{ "array": [2,3,6,8,8,4], "showIndices": true, "highlightIndices": [3, 4], "highlightIndicesGreen": [0,1,2,3,4], "specialIndices": [], "emptyCompIndices": [3] }

Insert key 7 into the correct position index=3.

{ "array": [2,3,6,7,8,4], "showIndices": true, "highlightIndicesGreen": [0,1,2,3,4], "specialIndices": [] }

Pass 5

Element at index=5 is the key.

{ "array": ["key : ",4], "showIndices": false, "specialIndices": [], "emptyIndices": [0] }

Our Goal: Take element 4 at index=5 and insert it into the sorted portion of array.

{ "array": [2,3,6,7,8,4], "showIndices": true, "highlightIndices": [5], "highlightIndicesGreen": [0,1,2,3,4], "specialIndices": [], "labels": { "5": "key" } }

Shift all elements greater than the key 4, on the left side of the key, one position to the right.

➜ 8 at index=4 is greater than key 4. Move it to right by one position.

{ "array": [2,3,6,7,8,8], "showIndices": true, "highlightIndices": [4, 5], "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [], "emptyCompIndices": [4] }

➜ 7 at index=3 is greater than key 4. Move it to right by one position.

{ "array": [2,3,6,7,7,8], "showIndices": true, "highlightIndices": [3, 4], "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [], "emptyCompIndices": [3] }

➜ 6 at index=2 is greater than key 4. Move it to right by one position.

{ "array": [2,3,6,6,7,8], "showIndices": true, "highlightIndices": [2, 3], "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [], "emptyCompIndices": [2] }

Insert key 4 into the correct position index=2.

{ "array": [2,3,4,6,7,8], "showIndices": true, "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [] }

Array is fully sorted.

{ "array": [2,3,4,6,7,8], "showIndices": false, "highlightIndicesGreen": [0,1,2,3,4,5], "specialIndices": [] }

⬅ Previous TopicSelection Sort

Next Topic ⮕Merge Sort

Comments

Loading comments...