Insertion Sort - Understanding with Visualization and Examples

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode Detailed Exmpl

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❯

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

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
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)

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": [] }