Insertion sort

Definition

Insertion sort is an in-place comparison-based sorting algorithm that builds the final sorted array one element at a time by repeatedly taking the next element and inserting it into its correct position within the already sorted part of the array.

In other words, at every step, the algorithm assumes the left side of the list is sorted, then inserts the next element into the correct location within that sorted section.

Main Content

1. Working Principle of Insertion Sort

The array is divided into two logical parts:
a sorted portion
an unsorted portion
The algorithm takes the first element as already sorted, then picks each next element from the unsorted portion and places it into the correct position in the sorted portion by shifting larger elements to the right.

Example:

Suppose the array is:

[7, 3, 5, 2]

Step-by-step:

Start with 7 as sorted.
Insert 3 before 7 → [3, 7, 5, 2]
Insert 5 between 3 and 7 → [3, 5, 7, 2]
Insert 2 at the beginning → [2, 3, 5, 7]

This method resembles inserting cards into a hand in sorted order.

2. Key Characteristics of Insertion Sort

In-place algorithm

: It does not require extra memory for another array. The rearrangement happens within the same list.

Stable sorting algorithm

: Equal elements keep their original order. This is important when sorting records by one field while preserving order of another field.

Adaptive behavior

: It performs very well when the input is already nearly sorted, because only a few comparisons and shifts are needed.

For example, if an array is:

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

Only one element is out of order, so insertion sort will finish quickly compared to more complex algorithms like quicksort or mergesort.

3. Time and Space Complexity

Best case time complexity

: O(n) when the array is already sorted. Each element is checked once with minimal shifting.

Average and worst case time complexity

: O(n²) when the array is in reverse order or highly unsorted. Every new element may need to be moved across many positions.

Space complexity

: O(1) because it uses only a constant amount of extra memory.

For example:

Best case: [1, 2, 3, 4, 5]
Worst case: [5, 4, 3, 2, 1]

In the worst case, every insertion may require shifting nearly all previously sorted elements.

Working / Process

Start from the second element of the array, because the first element is considered sorted.
Compare the current element with elements in the sorted portion, moving from right to left.
Shift all larger elements one position to the right, then insert the current element into the correct place.

Example process for [8, 4, 6, 2]:

Start: [8, 4, 6, 2]
4 compared with 8, shift 8 right → [4, 8, 6, 2]
6 compared with 8, shift 8 right, then place 6 → [4, 6, 8, 2]
2 compared with 8, 6, 4, shift all right, then place 2 → [2, 4, 6, 8]

Visual representation of the idea:

[ Sorted Part | Unsorted Part ]

Example during sorting:

[ 3, 5, 9 | 4, 8 ]

3, 5, 9 are already sorted
4 is taken and inserted between 3 and 5
8 is inserted between 5 and 9

This process continues until the entire array becomes sorted.

Advantages / Applications

Simple to understand and easy to implement, making it a common introductory sorting algorithm in computer science.
Efficient for small arrays and nearly sorted data, where its actual performance can be quite good.
Useful in practical situations such as:
sorting small batches of data
inserting new elements into an already sorted list
hybrid sorting algorithms, where insertion sort is used for small subarrays after a more advanced sort divides the data

Example applications:

Sorting a few student marks in a classroom program
Maintaining a short list of names in alphabetical order
Being used as a finishing step in optimized sorting systems for small data sections

Summary

Insertion sort builds a sorted list one element at a time.
It is simple, stable, and works in-place.
It is fast for small or nearly sorted input but slow for large unsorted input.
Important terms to remember
sorted portion
unsorted portion
shifting
stable sort
in-place algorithm