Insertion Sort

Builds the sorted array one element at a time by repeatedly taking an element from the unsorted portion and inserting it into its correct position in the sorted portion.

Algorithm Information

Time Complexity

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

Space Complexity

O(1)

Properties

• Stable sorting algorithm
• In-place sorting
• Adaptive (efficient for small datasets)
• Online (can sort as it receives data)
1/56
Speed: 1x

Algorithm Code

1function insertionSort(arr) {
2  const n = arr.length;
3  
4  for (let i = 1; i < n; i++) {
5    const key = arr[i];
6    let j = i - 1;
7    
8    // Move elements greater than key one position ahead
9    while (j >= 0 && arr[j] > key) {
10      arr[j + 1] = arr[j];
11      j--;
12    }
13    
14    // Insert key at correct position
15    arr[j + 1] = key;
16  }
17  
18  return arr;
19}

Variable State

i:1
j:0
n:7
key:34

Array Visualization

Watch how Insertion Sort builds the sorted portion one element at a time by inserting each element into its correct position

640
341
252
123
224
115
906

Statistics

Comparisons0
Shifts0
Step1 / 56

Legend

Comparing / Key Element
Shifting Elements
Sorted Portion
Unsorted

Starting Insertion Sort. The first element is considered sorted.

How Insertion Sort Works

Master insertion sort through detailed explanations, real-world analogies, and practical examples.

Algorithm Overview

Insertion Sort builds the final sorted array one element at a time. It works by taking elements from the unsorted portion and inserting them into their correct position within the already-sorted portion. This process continues until all elements have been inserted into their proper places.

🃏 Card Game Analogy

Think of sorting a hand of playing cards. You pick up cards one by one and insert each new card into its correct position among the cards you've already sorted in your hand. This is exactly how insertion sort works - it maintains a sorted portion and inserts new elements where they belong.

Step-by-Step Process

1

Start with Second Element

The first element is considered already "sorted". Begin with the second element as your "key" to insert into the sorted portion.

for (let i = 1; i < n; i++) {
  const key = arr[i]; // Element to insert
}
2

Compare and Shift

Compare the key with elements in the sorted portion, moving from right to left. Shift larger elements one position to the right to make space.

let j = i - 1;
while (j >= 0 && arr[j] > key) {
  arr[j + 1] = arr[j]; // Shift right
  j--;
}
3

Insert the Key

Once you find the correct position (where no more shifting is needed), insert the key element at that position.

Key Insight: The key is inserted exactly where it belongs in the sorted sequence!
4

Expand Sorted Portion

The sorted portion now includes one more element. Repeat the process with the next unsorted element until the entire array is sorted.

arr[j + 1] = key;

Complete Implementation

Here's the complete insertion sort implementation with detailed comments:

function insertionSort(arr) {
    const n = arr.length;
    
    // Start from second element (index 1)
    // First element is considered already sorted
    for (let i = 1; i < n; i++) {
        const key = arr[i];  // Current element to insert
        let j = i - 1;       // Start of sorted portion
        
        // Move elements greater than key one position ahead
        // This creates space for the key to be inserted
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // Shift element to the right
            j = j - 1;            // Move to previous element
        }
        
        // Insert key at its correct position
        arr[j + 1] = key;
        
        // Now arr[0...i] is sorted
    }
    
    return arr;
}

// Example with step-by-step trace:
const numbers = [5, 2, 4, 6, 1, 3];
console.log("Original:", numbers);

// Pass 1: Insert 2 into [5] → [2, 5, 4, 6, 1, 3]
// Pass 2: Insert 4 into [2, 5] → [2, 4, 5, 6, 1, 3]  
// Pass 3: Insert 6 into [2, 4, 5] → [2, 4, 5, 6, 1, 3]
// Pass 4: Insert 1 into [2, 4, 5, 6] → [1, 2, 4, 5, 6, 3]
// Pass 5: Insert 3 into [1, 2, 4, 5, 6] → [1, 2, 3, 4, 5, 6]

insertionSort(numbers);
console.log("Sorted:", numbers);

Key Concepts & Characteristics

✅ Advantages

  • •Simple implementation: Easy to code and understand
  • •Efficient for small data: Outperforms complex algorithms on small arrays
  • •Adaptive: O(n) performance on nearly sorted data
  • •Stable: Maintains relative order of equal elements
  • •In-place: Only requires O(1) extra memory
  • •Online: Can sort data as it's received

❌ Disadvantages

  • •Quadratic time: O(n²) for average and worst cases
  • •Many shifts: Elements may be moved multiple times
  • •Poor on large data: Becomes impractical for large datasets
  • •Reverse order worst: Maximum shifts needed for reverse-sorted data

🔄 Adaptive Behavior

Insertion sort is adaptive, meaning it performs significantly better on data that's already partially sorted. If the array is already sorted, it runs in O(n) time because no shifting is needed. This makes it excellent for maintaining sorted lists when new elements are occasionally added.

Complexity Analysis

Best Case

O(n)

Array is already sorted. Each element is compared once and no shifting occurs.

Average Case

O(n²)

Random data. On average, each element needs to be compared with half of the sorted portion.

Worst Case

O(n²)

Reverse sorted array. Each element must be compared with all elements in the sorted portion.

Mathematical Analysis

Best Case (Sorted): 1 + 1 + 1 + ... + 1 = n-1 = O(n)
Worst Case (Reverse): 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(n²)
Average Case: Each element compares with ~i/2 elements = n²/4 = O(n²)
Space Complexity: O(1) - Only uses a constant amount of extra space

When to Use Insertion Sort

✅ Ideal for:

  • • Small datasets: Arrays with < 50 elements
  • • Nearly sorted data: Takes advantage of adaptive behavior
  • • Online algorithms: Sorting data as it arrives
  • • Hybrid algorithms: Used in Timsort and Introsort for small subarrays
  • • Educational purposes: Teaching sorting concepts
  • • Simple implementation: When code simplicity matters

❌ Avoid for:

  • • Large datasets: O(n²) becomes prohibitively slow
  • • Random data: No performance advantages
  • • Reverse sorted data: Worst-case performance guaranteed
  • • Performance-critical systems: Better alternatives available
  • • Memory-sensitive applications: Too many element movements

🏭 Real-World Usage

Insertion sort is widely used as a subroutine in hybrid sorting algorithms. For example, Timsort (Python's default sort) and Introsort (C++'s std::sort) switch to insertion sort for small subarrays because it's faster than more complex algorithms on small data due to lower constant factors and better cache performance.