Implementation

Let’s code insertion sort. It’s straightforward with nested loops.

Complete Implementation

              function insertionSort(arr) {
const n = arr.length;

for (let i = 1; i < n; i++) {
  const current = arr[i];
  let j = i - 1;
  
  while (j >= 0 && arr[j] > current) {
    arr[j + 1] = arr[j];
    j--;
  }
  
  arr[j + 1] = current;
}

return arr;
}
            

              def insertion_sort(arr):
  n = len(arr)
  
  for i in range(1, n):
      current = arr[i]
      j = i - 1
      
      while j >= 0 and arr[j] > current:
          arr[j + 1] = arr[j]
          j -= 1
      
      arr[j + 1] = current
  
  return arr
            

Try It Yourself

Code Explanation

1. Outer loop: Starts at index 1 (first element is already “sorted”)
2. Save current: Store element to insert
3. Inner loop: Shift elements right while they’re greater
4. Insert: Place current element at correct position
5. In-place: Modifies original array

Edge Cases

• Empty array: Returns as-is (loop doesn’t run)
• Single element: Returns as-is (already sorted)
• Already sorted: Inner loop rarely runs, very efficient
• Reverse sorted: Inner loop runs maximum times, O(n²)

Optimizations

1. Binary search: Use binary search to find insertion position (reduces comparisons but not shifts)
2. Early termination: Stop inner loop early if no shifts needed
3. Sentinel: Use sentinel value to avoid boundary checks

Recursive Version

What’s Next?

Now that you can implement it, let’s analyze its performance and complexity.