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 <- 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

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

1. ✅ 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.

2. 🎴 Small Data Sets

   • It's simple and performs well on small input sizes, often outperforming more complex algorithms.
   • Example: Sorting a few user input values in form fields or dropdowns.

3. ♻️ Online Sorting

   • Insertion sort can sort real-time incoming data, as it doesn’t need the whole dataset to be available in advance.
   • Example: Ranking players as scores arrive during a live game.

4. 🧪 Teaching & Learning

   • It’s commonly used in computer science courses to teach basic sorting concepts due to its simplicity.
   • Example: Used in introductory algorithm lessons in schools and colleges.

5. 🔄 Linked Lists

   • Insertion sort can be efficiently used for sorting linked lists where shifting elements is cheap (just re-linking nodes).