Insertion Sort Implementation

JavaScript Implementation

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // Select element to be inserted
    let key = arr[i];
    let j = i - 1;
    
    // Move elements greater than key
    // to one position ahead
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // Insert the key in its correct position
    arr[j + 1] = key;
  }
  return arr;
}

// Usage example
let array = [12, 11, 13, 5, 6];
console.log(insertionSort(array)); // [5, 6, 11, 12, 13]

Python Implementation

def insertion_sort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    
    return arr

# Test
array = [12, 11, 13, 5, 6]
print(insertion_sort(array))  # [5, 6, 11, 12, 13]

Key Implementation Details:

• Inner Loop Direction: The inner loop scans backward through the sorted portion, which is crucial for insertion sort's efficiency.
• Element Shifting: Rather than swapping adjacent elements (as in bubble sort), insertion sort shifts elements one position right to make room for the key element.
• Early Termination: The inner loop stops as soon as it finds an element smaller than or equal to the key, which gives insertion sort its adaptive property.