Dev.to

Insertion Sort

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. It works just like how we sort playing cards in our hands: We pick one card at a time from the unsorted pile. Then, we place it in the correct position among the already sorted cards. This process repeats until all the cards (or elements) are in order. Working of Insertion Sort Suppose we need to sort the following array. 1. The first element in the array is assumed to be sorted. Take the second element and store it separately in key. Compare key with the first element. If the first element is greater than key, then place the key in the position of the first element. 2. Now, the first two elements are sorted. Take the third element and compare it with the elements to its left. Place it just after the element that is smaller than it. If no smaller element is found, place it at the beginning of the array. 3. Similarly, place every unsorted element at its correct position. Insertion Sort Algorithm insertionSort(array) mark first element as sorted for each unsorted element X 'extract' the element X for j X move sorted element to the right by 1 break loop and insert X here end insertionSort Insertion Sort Code function insertionSort(arr) { let n = arr.length; for (let i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return arr; } console.log(insertionSort([15, 6, 2, 3, 1])); Insertion Sort Complexity Time Complexity Best O(n) Worst O(n²) Average O(n²) Space Complexity O(1) Stability Yes 1. Time Complexities Worst Case Complexity: O(n²) If we want to sort in ascending order and the array is in descending order then the worst case occurs. Best Case Complexity: O(n) When the array is already sorted, the outer loop runs for n number of times whereas the inner loop does not run at all. So, there are only n number of comparisons. Thus, complexity is linear. Average Case Complexity: O(n²) It occurs when the elements of the array are in jumbled order (neither ascending nor descending). 2. Space Complexity Space complexity is O(1). Insertion Sort Applications ✅ Nearly Sorted Arrays Insertion sort is very efficient for arrays that are already mostly sorted. It runs in O(n) time in such cases. Example: Sorting attendance records that only get updated daily.

Apr 9, 2025 - 10:20

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

It works just like how we sort playing cards in our hands:

We pick one card at a time from the unsorted pile.
Then, we place it in the correct position among the already sorted cards.

This process repeats until all the cards (or elements) are in order.

Working of Insertion Sort

Suppose we need to sort the following array.

1. The first element in the array is assumed to be sorted. Take the
second element and store it separately in key.

Compare key with the first element. If the first element is greater
than key, then place the key in the position of the first element.

2. Now, the first two elements are sorted.

Take the third element and compare it with the elements to its left. Place it just after the element that is smaller than it. If no smaller element is found, place it at the beginning of the array.

3. Similarly, place every unsorted element at its correct position.

Insertion Sort Algorithm

insertionSort(array)
  mark first element as sorted
  for each unsorted element X
    'extract' the element X
    for j <- lastSortedIndex down to 0
      if current element j > X
        move sorted element to the right by 1
    break loop and insert X here
end insertionSort

Insertion Sort Code

function insertionSort(arr) {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];

    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }

  return arr;
}

console.log(insertionSort([15, 6, 2, 3, 1]));

Insertion Sort Complexity

Time Complexity
Best	O(n)
Worst	O(n²)
Average	O(n²)
Space Complexity	O(1)
Stability	Yes

1. Time Complexities

Worst Case Complexity: O(n²)
If we want to sort in ascending order and the array is in descending order then the worst case occurs.
Best Case Complexity: O(n)
When the array is already sorted, the outer loop runs for n number of times whereas the inner loop does not run at all. So, there are only n number of comparisons. Thus, complexity is linear.
Average Case Complexity: O(n²)
It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

Space complexity is O(1).

Insertion Sort Applications

✅ Nearly Sorted Arrays
- Insertion sort is very efficient for arrays that are already mostly sorted. It runs in O(n) time in such cases.
- Example: Sorting attendance records that only get updated daily.