Summary
| Algorithm Name | Insertion Sort | |
| Category |  Sorting Algorithms | |
| Core Technique | Find the correct position of an element and insert it there. | |
| Best Case Time Complexity | Ω(n) | Linear |
| Average Case Time Complexity | Θ(n^2) | Quadratic |
| Worst Case Time Complexity | O(n^2) | Quadratic |
| Space / Memory Complexity | O(1) | In-place |
Intro
Insertion Sort repeatedly takes the next element and inserts it into its correct position within the sorted part of the array.
Basically, it finds the correct position of an element and inserts it in that correct position. In that process, it shifts the rest of the elements to make space for that key element.
This is not a very efficient sorting algorithm, but it is easy to understand, as there are lots of swapping/shifting operations involved.
Algorithm Visualizer
Here is the visualizer for the Insertion sort algorithm to demonstrate the process clearly.
Enter integers separated by commas(Example: 5,3,8,4,2,7,1,9,6).
Click ‘Start Sorting’ to visualize insertion sort.
Click ‘Reset’ to clear and re-enter numbers.
Click ‘Start Sorting’ to visualize insertion sort.
Click ‘Reset’ to clear and re-enter numbers.
Insertion Sort Visualizer Logs…
Implementation Steps
Here are teh steps we should follow to implement Insertion sort-
- Start from the second element (index 1), treating the first element as already sorted.
- Pick the current element (key) to be placed in the sorted part.
- Compare the key with elements in the sorted portion (to its left).
- Shift all elements that are greater than the key one position to the right.
- Insert the key into its correct position.
- Repeat steps 2–5 for all remaining elements until the array is sorted.
Pseudocode
Here is the pseudocode for Insertion sort. It will make the implementation steps clear-
// Insertion Sort Pseudocode
procedure InsertionSort(array A)
n = length(A)
for i from 1 to n-1 do
key = A[i]
j = i - 1
// Move/shift elements of A[0..i-1],
// that are greater than key, to one position ahead
while j >= 0 and A[j] > key do
A[j+1] = A[j]
j = j - 1
end while
A[j+1] = key
end for
end procedureImplementation
// File: algorithm/js/sorting/insertion-sort/insertion-sort.js
// Insertion Sort implementation
/**
* Insertion Sort Algorithm
* @param {number[]} arr - The array to be sorted
* @returns {number[]} - The sorted array
*/
function insertionSort(arr) {
const n = arr.length;
// Iterate over each element starting from the second
for (let i = 1; i < n; i++) {
// Save the current element as key
let key = arr[i];
let j = i - 1;
// Shift elements greater than key to the right
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert the key element at its correct position
arr[j + 1] = key;
}
return arr;
}
export default insertionSort;Demo
// File: algorithm/js/sorting/insertion-sort/insertion-sort.demo.js
// Demo for Insertion Sort
import insertionSort from "./insertion-sort.js";
// Demo cases
const demoCases = [
{ name: "Random order", arr: [5, 3, 8, 4, 2] },
{ name: "Already sorted", arr: [1, 2, 3, 4, 5] },
{ name: "Reverse sorted", arr: [5, 4, 3, 2, 1] },
{ name: "With duplicates", arr: [3, 1, 2, 3, 2, 1] },
{ name: "Single element", arr: [42] },
{ name: "Empty array", arr: [] },
{ name: "All identical", arr: [7, 7, 7, 7] },
{ name: "Negative numbers", arr: [3, -1, -4, 2, 0] },
{ name: "Large and small numbers", arr: [999999, -999999, 0, 1, -1] },
{ name: "Non-integer numbers", arr: [2.5, 3.1, 1.2, 4.8] },
{ name: "Two elements", arr: [2, 1] },
{ name: "Single repeated value and others", arr: [1, 2, 1, 3, 1] }
];
demoCases.forEach(({ name, arr }) => {
const inputArr = [...arr];
const sortedArr = insertionSort(inputArr);
console.log(`\nCase: ${name}`);
console.log("Input Array:", arr);
console.log("Sorted Array:", sortedArr);
});Output:
Case: Random order
Input Array: [ 5, 3, 8, 4, 2 ]
Sorted Array: [ 2, 3, 4, 5, 8 ]
Case: Already sorted
Input Array: [ 1, 2, 3, 4, 5 ]
Sorted Array: [ 1, 2, 3, 4, 5 ]
Case: Reverse sorted
Input Array: [ 5, 4, 3, 2, 1 ]
Sorted Array: [ 1, 2, 3, 4, 5 ]
Case: With duplicates
Input Array: [ 3, 1, 2, 3, 2, 1 ]
Sorted Array: [ 1, 1, 2, 2, 3, 3 ]
Case: Single element
Input Array: [ 42 ]
Sorted Array: [ 42 ]
Case: Empty array
Input Array: []
Sorted Array: []
Case: All identical
Input Array: [ 7, 7, 7, 7 ]
Sorted Array: [ 7, 7, 7, 7 ]
Case: Negative numbers
Input Array: [ 3, -1, -4, 2, 0 ]
Sorted Array: [ -4, -1, 0, 2, 3 ]
Case: Large and small numbers
Input Array: [ 999999, -999999, 0, 1, -1 ]
Sorted Array: [ -999999, -1, 0, 1, 999999 ]
Case: Non-integer numbers
Input Array: [ 2.5, 3.1, 1.2, 4.8 ]
Sorted Array: [ 1.2, 2.5, 3.1, 4.8 ]
Case: Two elements
Input Array: [ 2, 1 ]
Sorted Array: [ 1, 2 ]
Case: Single repeated value and others
Input Array: [ 1, 2, 1, 3, 1 ]
Sorted Array: [ 1, 1, 1, 2, 3 ]Tests
// File: algorithm/js/sorting/insertion-sort/insertion-sort.test.js
// Tests for Insertion Sort
import { describe, it, expect } from "vitest";
import insertionSort from "./insertion-sort.js";
describe("Insertion Sort", () => {
it("should sort an array of numbers in ascending order", () => {
const sortedArr = insertionSort([5, 3, 8, 4, 2]);
expect(sortedArr).toEqual([2, 3, 4, 5, 8]);
});
it("should handle an already sorted array", () => {
const sortedArr = insertionSort([1, 2, 3, 4, 5]);
expect(sortedArr).toEqual([1, 2, 3, 4, 5]);
});
it("should handle an array with duplicate values", () => {
const sortedArr = insertionSort([3, 1, 2, 3, 2, 1]);
expect(sortedArr).toEqual([1, 1, 2, 2, 3, 3]);
});
it("should handle an empty array", () => {
const sortedArr = insertionSort([]);
expect(sortedArr).toEqual([]);
});
it("should handle an array with a single element", () => {
const sortedArr = insertionSort([42]);
expect(sortedArr).toEqual([42]);
});
it("should handle an array with all identical elements", () => {
const sortedArr = insertionSort([7, 7, 7, 7]);
expect(sortedArr).toEqual([7, 7, 7, 7]);
});
it("should handle an array with negative numbers", () => {
const sortedArr = insertionSort([3, -1, -4, 2, 0]);
expect(sortedArr).toEqual([-4, -1, 0, 2, 3]);
});
it("should handle an array with very large and very small numbers", () => {
const sortedArr = insertionSort([999999, -999999, 0, 1, -1]);
expect(sortedArr).toEqual([-999999, -1, 0, 1, 999999]);
});
it("should handle an array with non-integer numbers", () => {
const sortedArr = insertionSort([2.5, 3.1, 1.2, 4.8]);
expect(sortedArr).toEqual([1.2, 2.5, 3.1, 4.8]);
});
it("should handle an array with only two elements", () => {
const sortedArr = insertionSort([2, 1]);
expect(sortedArr).toEqual([1, 2]);
});
it("should handle an array with a single repeated value and others", () => {
const sortedArr = insertionSort([1, 2, 1, 3, 1]);
expect(sortedArr).toEqual([1, 1, 1, 2, 3]);
});
});Source Code
| Source Code of | Implementation Code | Demo Code | Test Case Code | Benchmark Code |
|---|---|---|---|---|
| Selection Sort Visualizer | Insertion Sort Visualizer – GitHub | |||
| Selection Sort Pseudocode | Insertion Sort Pseudocode – GitHub | |||
| Selection Sort Implementation in JS | Insertion Sort Implementation in JS – GitHub | Insertion Sort Demo in JS – GitHub | Insertion Sort Tests in JS – GitHub | Insertion Sort Benchmark in JS – GitHub |