42.implement-Insertion-Sort.md

42. implement Insertion Sort

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It builds the final sorted array one element at a time by repeatedly picking the next element and inserting it into its correct position among the previously sorted elements.

Problem

https://bigfrontend.dev/problem/implement-Insertion-Sort

Problem Description

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work.

Now you are asked to implement Insertion Sort, which sorts an integer array in ascending order.

Do it in-place, no need to return anything.

Follow-up

What is time cost for average / worst case ? Is it stable?

Solution

/**
 * @param {number[]} arr
 */
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i];
    let j = i - 1;
    while (j >= 0 && currentVal < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = currentVal;
  }
}

Use Cases:

1. Small Data Sets: Efficient for small datasets due to its simplicity and low overhead.
2. Nearly Sorted Data: Performs very well on nearly sorted data or when the data is already sorted.
3. Online Sorting: Suitable for scenarios where the list is being received in a streaming fashion, as it can sort the list as elements arrive.