Insertion Sort Algorithm Explained
Insertion Sort is a simple comparison-based sorting algorithm that builds a sorted array one element at a time. It works by taking each element from the unsorted part of the array and inserting it into its correct position inside the sorted part.
Insertion Sort is easy to understand, easy to implement, and very useful for learning how sorting algorithms think. Although it is not the fastest sorting algorithm for large datasets, it performs well on small arrays or arrays that are already almost sorted.
Introduction
Sorting is one of the most important operations in computer science. Developers use sorting when they need to organize numbers, names, dates, prices, scores, search results, database records, or any collection of comparable values.
After learning basic sorting algorithms such as Bubble Sort and Selection Sort, Insertion Sort gives developers another important idea: instead of repeatedly swapping neighboring values or searching for the smallest element, the algorithm inserts each value into the correct place, similar to how people arrange playing cards in their hands.
This makes Insertion Sort a very intuitive algorithm. When a new value is picked, it is compared with the values before it. If previous values are larger, they are shifted to the right until the correct position is found.
What Is Insertion Sort?
Insertion Sort is a sorting algorithm that divides the array into two parts: a sorted part and an unsorted part. At the beginning, the first element is considered sorted. Then the algorithm takes the next element and inserts it into the correct position inside the sorted part.
The process continues until every element has been inserted into its correct position.
The main idea is simple:
Start from the second element.
Compare it with elements before it.
Shift larger elements one position to the right.
Insert the current element into the correct position.
Repeat until the array is sorted.
Insertion Sort is called “insertion” because each element is inserted into its correct place in the sorted part of the array.
How Insertion Sort Works
Insertion Sort works by gradually expanding the sorted part of the array. The algorithm assumes that the first element is already sorted because a single element is always sorted by itself.
Then it starts with the second element and stores it as the current value. The algorithm compares this current value with the elements before it. If an earlier element is greater than the current value, that earlier element is shifted to the right.
When the correct position is found, the current value is placed there. This continues until all elements are processed.
In simple words, Insertion Sort asks one repeated question:
Where should this current element be inserted inside the already sorted part?
Manual Run Example
Let us manually sort the following array using Insertion Sort:
[5, 3, 8, 4, 2]At the beginning, the first element is considered sorted:
Sorted part: [5]
Unsorted part: [3, 8, 4, 2]Pass 1
The current element is 3. We compare it with the previous element 5.
Since 5 is greater than 3, we shift 5 one position to the right.
Before insertion:
[5, 3, 8, 4, 2]
Shift 5 to the right:
[5, 5, 8, 4, 2]
Insert 3:
[3, 5, 8, 4, 2]Now the sorted part is:
[3, 5]Pass 2
The current element is 8. We compare it with 5.
Since 5 is not greater than 8, no shifting is needed. The element 8 is already in the correct position.
Before insertion:
[3, 5, 8, 4, 2]
After insertion:
[3, 5, 8, 4, 2]Now the sorted part is:
[3, 5, 8]Pass 3
The current element is 4. We compare it with the previous elements in the sorted part.
First, 8 is greater than 4, so 8 is shifted to the right. Then 5 is greater than 4, so 5 is shifted to the right. The value 3 is not greater than 4, so we insert 4 after 3.
Before insertion:
[3, 5, 8, 4, 2]
Shift 8:
[3, 5, 8, 8, 2]
Shift 5:
[3, 5, 5, 8, 2]
Insert 4:
[3, 4, 5, 8, 2]Now the sorted part is:
[3, 4, 5, 8]Pass 4
The current element is 2. We compare it with all previous elements in the sorted part.
Since 8, 5, 4, and 3 are all greater than 2, each one is shifted to the right. Then 2 is inserted at the beginning.
Before insertion:
[3, 4, 5, 8, 2]
Shift 8:
[3, 4, 5, 8, 8]
Shift 5:
[3, 4, 5, 5, 8]
Shift 4:
[3, 4, 4, 5, 8]
Shift 3:
[3, 3, 4, 5, 8]
Insert 2:
[2, 3, 4, 5, 8]The array is now sorted.
Final Sorted Array
[2, 3, 4, 5, 8]This manual run shows the core behavior of Insertion Sort. The algorithm does not search for the smallest element like Selection Sort. Instead, it takes one element at a time and inserts it into the correct position among the previous elements.
Insertion Sort Algorithm Steps
The algorithm can be described using these steps:
Assume the first element is already sorted.
Start from the second element.
Store the current element in a temporary variable.
Compare the current element with elements before it.
Shift larger elements one position to the right.
Insert the current element into the correct position.
Repeat until the end of the array.
This step-by-step behavior makes Insertion Sort simple and predictable.
Pseudocode
for i from 1 to length(array) - 1:
current = array[i]
j = i - 1
while j >= 0 and array[j] > current:
array[j + 1] = array[j]
j = j - 1
array[j + 1] = currentThe outer loop chooses each element from the unsorted part. The inner loop shifts larger elements to the right until the correct insertion position is found.
Insertion Sort Example in PHP
Here is a clean PHP implementation of Insertion Sort:
<?php
function insertionSort(array $numbers): array
{
$length = count($numbers);
for ($i = 1; $i < $length; $i++) {
$current = $numbers[$i];
$j = $i - 1;
while ($j >= 0 && $numbers[$j] > $current) {
$numbers[$j + 1] = $numbers[$j];
$j--;
}
$numbers[$j + 1] = $current;
}
return $numbers;
}
$numbers = [5, 3, 8, 4, 2];
$sortedNumbers = insertionSort($numbers);
print_r($sortedNumbers);The output will be:
Array
(
[0] => 2
[1] => 3
[2] => 4
[3] => 5
[4] => 8
)This implementation creates a sorted version of the array and returns it. The shifting happens inside the while loop, while the final insertion happens after the loop ends.
Insertion Sort Example in JavaScript
Here is the same algorithm implemented in JavaScript:
function insertionSort(numbers) {
for (let i = 1; i < numbers.length; i++) {
const current = numbers[i];
let j = i - 1;
while (j >= 0 && numbers[j] > current) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = current;
}
return numbers;
}
const numbers = [5, 3, 8, 4, 2];
console.log(insertionSort(numbers));The output will be:
[2, 3, 4, 5, 8]The JavaScript version follows the same logic as the PHP version. The syntax changes, but the algorithmic idea remains exactly the same.
Why Insertion Sort Shifts Instead of Swapping
Insertion Sort usually shifts elements instead of repeatedly swapping them. This makes the algorithm easier to understand and often more efficient than performing many swaps.
When the current value is smaller than previous values, the algorithm moves those previous values one position to the right. After the right position is open, the current value is inserted there.
For example, if we insert 4 into this sorted part:
[3, 5, 8]The algorithm shifts 8 and 5 to the right, then places 4 between 3 and 5:
[3, 4, 5, 8]This behavior is similar to arranging cards in your hand. You make space for the new card, then place it in the correct location.
Time Complexity of Insertion Sort
Time complexity describes how the running time of an algorithm grows as the input size increases. For Insertion Sort, the performance depends heavily on how sorted the input array already is.
Insertion Sort has three important time complexity cases:
Best case: O(n)
Average case: O(n²)
Worst case: O(n²)
These cases happen because the inner loop may run very little or many times depending on the order of the elements.
Best Case Time Complexity: O(n)
The best case happens when the array is already sorted.
[1, 2, 3, 4, 5]In this case, every current element is already greater than the element before it. The algorithm still checks each element once, but it does not need to shift anything.
Because the algorithm only performs a simple pass through the array, the best case time complexity is:
O(n)This is one of the advantages of Insertion Sort. It can be very efficient when the data is already sorted or nearly sorted.
Average Case Time Complexity: O(n²)
The average case happens when the elements are in random order.
[5, 1, 4, 2, 8]In this situation, some elements may need small shifts, while others may need larger shifts. On average, each element may be compared with several previous elements.
As the array grows, the number of comparisons and shifts grows roughly quadratically. Therefore, the average case time complexity is:
O(n²)This means Insertion Sort becomes slow for large arrays with random order.
Worst Case Time Complexity: O(n²)
The worst case happens when the array is sorted in reverse order.
[5, 4, 3, 2, 1]In this case, every new element must be moved all the way to the beginning of the sorted part. This creates the maximum number of comparisons and shifts.
For example, the second element may need one shift, the third element may need two shifts, the fourth element may need three shifts, and so on.
The total amount of work becomes approximately:
1 + 2 + 3 + ... + (n - 1)This grows as n², so the worst case time complexity is:
O(n²)Space Complexity of Insertion Sort
Insertion Sort does not require an additional array to sort the elements. It only uses a few extra variables such as the current value and index counters.
Because of this, the space complexity is:
O(1)This means Insertion Sort is an in-place sorting algorithm. It sorts the array using constant extra memory.
Is Insertion Sort Stable?
Insertion Sort is a stable sorting algorithm when implemented correctly.
A stable sorting algorithm preserves the relative order of equal elements. For example, if two students have the same grade, a stable sort keeps them in the same relative order they had before sorting.
Insertion Sort is stable because it only shifts elements that are greater than the current element. It does not move equal elements before each other when the comparison uses:
array[j] > currentIf the comparison is changed to:
array[j] >= currentthen the algorithm may become unstable because equal values could be shifted unnecessarily.
Insertion Sort vs Bubble Sort
Insertion Sort and Bubble Sort are both simple sorting algorithms, and both have average and worst case time complexity of O(n²). However, Insertion Sort is often more practical for small or nearly sorted datasets.
Bubble Sort repeatedly compares neighboring elements and swaps them if they are in the wrong order. Insertion Sort builds a sorted part and inserts each new element into the correct place.
In practice, Insertion Sort usually performs fewer operations than Bubble Sort because it shifts elements directly into position instead of repeatedly swapping adjacent values.
Insertion Sort vs Selection Sort
Selection Sort repeatedly finds the smallest element from the unsorted part and places it at the beginning. Insertion Sort takes one element at a time and inserts it into the sorted part.
Both algorithms have O(n²) average and worst case time complexity, but they behave differently.
Selection Sort performs fewer swaps.
Insertion Sort performs better on nearly sorted data.
Insertion Sort is stable when implemented correctly.
Selection Sort is usually not stable unless modified.
Insertion Sort can stop shifting early when the correct position is found.
This makes Insertion Sort more adaptive than Selection Sort.
When Should Developers Use Insertion Sort?
Developers should use Insertion Sort when the dataset is small, nearly sorted, or when simplicity is more important than high performance.
Insertion Sort is useful when:
The array size is small.
The data is already almost sorted.
The algorithm needs to be simple and easy to understand.
Extra memory usage should be minimal.
A stable sorting algorithm is needed.
The sorting operation is part of an educational example.
For large datasets, developers usually prefer more efficient algorithms such as Merge Sort, Quick Sort, Heap Sort, or built-in sorting functions provided by programming languages.
When Not to Use Insertion Sort
Insertion Sort should not be used when sorting large random datasets where performance is important. Because its average and worst case time complexity is O(n²), the algorithm can become slow as the input size grows.
For example, sorting 10 elements with Insertion Sort is simple and fast. Sorting 1,000,000 random elements with Insertion Sort is usually a bad idea because the number of comparisons and shifts can become extremely large.
In production systems, developers should usually use optimized built-in sorting functions unless they have a specific reason to implement a sorting algorithm manually.
Common Mistakes When Implementing Insertion Sort
Beginners often make mistakes when implementing Insertion Sort because the algorithm requires careful index handling.
Common mistakes include:
Starting the outer loop from index 0 instead of index 1.
Forgetting to store the current value before shifting elements.
Using the wrong comparison condition inside the while loop.
Forgetting to insert the current value after shifting.
Decreasing the wrong index inside the loop.
Using
>=instead of>and losing stability.
The most important detail is to store the current value before shifting. Otherwise, the value may be overwritten during the shifting process.
Practical Example: Sorting Product Prices
Imagine a small e-commerce feature where a few product prices need to be sorted from lowest to highest. If the number of products is small, Insertion Sort can solve the problem in a simple way.
<?php
$prices = [49.99, 19.99, 99.99, 29.99];
function sortPrices(array $prices): array
{
for ($i = 1; $i < count($prices); $i++) {
$currentPrice = $prices[$i];
$j = $i - 1;
while ($j >= 0 && $prices[$j] > $currentPrice) {
$prices[$j + 1] = $prices[$j];
$j--;
}
$prices[$j + 1] = $currentPrice;
}
return $prices;
}
print_r(sortPrices($prices));The sorted result will be:
[19.99, 29.99, 49.99, 99.99]This example is simple, but it shows how Insertion Sort can be connected to real application data.
Practical Checklist for Understanding Insertion Sort
Before moving to more advanced sorting algorithms, developers should be able to answer these questions:
Why does Insertion Sort start from the second element?
What is the difference between the sorted part and the unsorted part?
Why do we store the current value before shifting?
When does the inner while loop stop?
Why is the best case O(n)?
Why is the worst case O(n²)?
Why is the space complexity O(1)?
Why is Insertion Sort stable?
If these points are clear, the developer has understood the real logic behind Insertion Sort, not just memorized the code.
Advantages of Insertion Sort
Insertion Sort has several advantages that make it useful in specific situations.
It is simple to understand and implement.
It performs well on small datasets.
It is efficient for nearly sorted arrays.
It is an in-place sorting algorithm.
It is stable when implemented correctly.
It has a best case time complexity of O(n).
These advantages make it a good algorithm for education and for small practical cases.
Disadvantages of Insertion Sort
Insertion Sort also has important limitations.
It is inefficient for large random datasets.
Its average case time complexity is O(n²).
Its worst case time complexity is O(n²).
It may require many shifts when the array is reversed.
It is usually slower than advanced sorting algorithms for large inputs.
Because of these limitations, Insertion Sort is not usually the best choice for large-scale production sorting.
Conclusion
Insertion Sort is a simple and practical sorting algorithm that builds the sorted array one element at a time. It works by taking each element from the unsorted part and inserting it into the correct position inside the sorted part.
The algorithm is easy to understand because it behaves like arranging cards in order. It shifts larger elements to the right and places the current element where it belongs.
Insertion Sort has a best case time complexity of O(n) when the array is already sorted, and an average and worst case time complexity of O(n²). Its space complexity is O(1), which means it sorts in place without requiring extra memory.
Although Insertion Sort is not ideal for large random datasets, it is excellent for learning algorithmic thinking, understanding comparisons and shifts, and handling small or nearly sorted arrays. For developers studying data structures and algorithms, Insertion Sort is an important step toward understanding more advanced sorting techniques.
