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❯

Insertion Sort works by building a sorted portion of the array one element at a time. It starts with the second element and moves backward through the sorted portion to find the right place to insert the current element.

Case 1: Normal Unsorted Input
For an array like [5, 2, 4, 6, 1, 3], the algorithm compares each element (starting from index 1) with the ones before it and shifts them to make space if needed. Over time, smaller elements move toward the front and larger ones settle toward the end, resulting in a sorted array.

Case 2: Already Sorted Input
In a best-case scenario such as [1, 2, 3, 4], the key is always greater than or equal to its previous element. No shifting is needed, and the algorithm only performs comparisons. This leads to faster execution — linear time complexity in this case.

Case 3: Reverse Sorted Input
In the worst-case scenario like [5, 4, 3, 2, 1], every new element is smaller than the elements before it. So, the entire sorted part must be shifted right to make room. This takes the maximum number of operations and results in a quadratic time complexity.

Case 4: All Elements Are the Same
If the array contains identical elements like [2, 2, 2, 2], comparisons are made but no elements are shifted. The result remains the same as the input, and it performs better than the worst case but not as fast as the best case.

Case 5: Single Element or Empty Array
A single-element array like [7] or an empty array [] are both considered already sorted. The algorithm will detect this quickly and perform no meaningful operations.

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