Insertion Sort

Insertion Sort is a comparison-based sorting algorithm that builds the sorted array one element at a time.

It assumes the first element is already sorted, then repeatedly takes the next element and inserts it into its correct position within the sorted portion of the array.

Insertion Sort Demo

Array Input

Comma or space separated · 2-16 numbers · 1-999 each

Speed

Pass1

Step 1 / 0

—

Unsorted

Comparing

Swapping

Sorted

Min / Key

Inserting

1. What is Insertion Sort?

Insertion Sort processes the array from left to right.

It takes the next element from the unsorted part,
inserts it into the correct position in the sorted part.

2. Dry Run Insertion Sort.

Input: 96 43 74 72 46 Output: 43 46 72 74 96

arr[0] = 96
arr[1] = 43
arr[2] = 74
arr[3] = 72
arr[4] = 46

Pass 1:

Key = 43
Insert before 96
Result: 43 96 74 72 46

Pass 2:

Key = 74
Insert after 43
Result: 43 74 96 72 46

Pass 3:

Key = 72
Shift 96 and insert before it
Result: 43 74 72 96 46

Pass 4:

Key = 46
Shift 96 72 74 and insert before them
Result: 43 46 72 74 96

3. Code Implementation

Example:

insertion-sort.cpp

#include <iostream>
 
using namespace std;
 
void insertionSort(int arr[], int n)
{
    for (int i = 1; i < n; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j] < arr[j - 1])
            {
                swap(arr[j], arr[j - 1]);
            }
            else
            {
                break;
            }
        }
    }
}
 
void printArray(int arr[], int n, string msg = "")
{
    cout << msg << endl;
 
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main()
{
    int arr[] = {51, 14, 33, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printArray(arr, n, "Original array:");
    
    insertionSort(arr, n);
    printArray(arr, n, "Sorted array(asc):");
 
    return 0;
}

Output:

Original array:
51 14 33 2 11
Sorted array(asc):
2 11 14 33 51

4. What is the time complexity of Insertion Sort?

Best: O(n)
Average: O(n²)
Worst: O(n²)

Because:

Best case occurs when the array is already sorted.
Worst case occurs when the array is sorted in reverse.

5. What is the space complexity?

O(1)

6. Is Insertion Sort stable?

Yes, Equal elements remain in the same relative order.

7. Is Insertion Sort adaptive?

Yes, it runs faster when the array is nearly sorted.

8. Why is Insertion Sort called “Insertion” Sort?

Because it inserts each element into the correct place in the sorted portion of the array.

9. When is Insertion Sort useful?

Small arrays.
Nearly sorted data.
When stability matters.

10. How many shifts does Insertion Sort make?

Worst case: O(n²) shifts.

In the best case, it only checks each element once.

11. Differences between bubble, insertion & selection sort.

Feature	Bubble Sort	Insertion Sort	Selection Sort
Basic Idea	Repeatedly swap adjacent elements if they are in the wrong order.	Insert each element into its correct position in the sorted part.	Find the minimum element and place it at its correct position.
How It Works	Largest element "bubbles" to the end in each pass.	Builds a sorted portion one element at a time.	Selects the smallest element from the unsorted portion.
Best Case	O(n)	O(n)	O(n²)
Average Case	O(n²)	O(n²)	O(n²)
Worst Case	O(n²)	O(n²)	O(n²)
Space Complexity	O(1)	O(1)	O(1)
Stable?	✅ Yes	✅ Yes	❌ No
Adaptive?	✅ Yes	✅ Yes	❌ No
Number of Swaps	High	Low (mostly shifts)	Minimum
Best For	Learning sorting basics.	Small or nearly sorted arrays.	When minimizing swaps is important.
Real-Life Analogy	Bubbles rising to the surface.	Arranging playing cards in your hand.	Picking the smallest item repeatedly from a pile.

Sorting Algorithms