Speed:

Insertion Sort

Best: O(n)Worst: O(n²)Stable & Adaptive

🃏How Insertion Sort Works

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. It works similarly to how you might sort playing cards in your hands.

The algorithm divides the array into two parts:

Sorted portion: Elements at the beginning (initially just the first element)
Unsorted portion: Remaining elements to be processed
For each element in the unsorted portion, find its correct position in the sorted portion
Shift elements as needed and insert the current element

💻Implementation

// Insertion Sort Implementation
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    
    // Move elements of arr[0..i-1] that are greater than key
    // one position ahead of their current position
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
  return arr;
}

// Alternative with binary search for position finding
function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let left = 0, right = i;
    
    // Find position to insert using binary search
    while (left < right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] > key) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    
    // Shift elements and insert
    for (let j = i - 1; j >= left; j--) {
      arr[j + 1] = arr[j];
    }
    arr[left] = key;
  }
  return arr;
}

📊Performance Analysis

Time Complexity

• Best case: O(n) - already sorted
• Average case: O(n²)
• Worst case: O(n²) - reverse sorted
• Space: O(1) in-place

Key Properties

• Stable: maintains relative order
• Adaptive: efficient for nearly sorted data
• Online: can sort data as it arrives
• In-place: requires only O(1) extra memory

🎯 Best Use Cases

• Small datasets (typically n < 50)
• Nearly sorted arrays
• Online algorithms (data arrives over time)
• Hybrid sorting (part of quicksort/mergesort)
• Simple implementation needed

🔄 Compared to Other Sorts

• vs Bubble Sort: More efficient, fewer swaps
• vs Selection Sort: Adaptive, better for partial sorting
• vs Quick Sort: Better for small arrays, stable
• vs Merge Sort: In-place, but slower for large data