Description

Good for data sets that are partially sorted
Suitable for small data sets

# Time & Space Complexity

Time:
- Best: O(n)
- Average: O(n^2)
- Worst: O(n^2)
Space:
- O(1)

# Implementation

javascript

function insertionSort(array) {
  for(let i=1; i<array.length; i++) {
    // Value that is going to be sorted
    const key = array[i];
    // Index of comparing value
    let pointer = i;

    /** 
     * Stop looping if:
     * 1. pointer is less than 0 (finished searching)
     * 2. comparing value is smaller than key (found index to move to)
     */
    while(pointer >= 0 && array[pointer] > key) {
      // Move array element to right of their current index
      array[pointer + 1] = array[pointer]; 
      pointer--;
    }

    // Put the key at the sorted position
    array[pointer + 1] = key;
  }
}

More explanation on the above implementation here.

# Possible Test Cases

javascript

const array1 = [] // Given array is empty
const array2 = [3] // Given array contains only a single element
const array3 = [0, 0, 0, 0] // Given array contains only zeros
const array4 = [2, 2, 2, 2] // Given array contains same elements
const array5 = [1, 2, 3, 4, 5] // Given array is already sorted
const array6 = [5, 4, 3, 2, 1] // Given array is reversed
const array7 = [-2, -5, 3, 1, 0] // Given array contain both positive and negative numbers
const array8 = generateRandom(10000) // Given array contains large number of elements

javascript

const generateRandom = (count) => {
  // Create array of integers
  let nums = [...Array(count).keys()];

  // Shuffle
  for (let i = nums.length - 1; i > 0; i--) {
    let randomIndex = Math.floor(Math.random() * i) % i;

    // Swap
    let temp = nums[i];
    nums[i] = nums[randomIndex];
    nums[randomIndex] = temp;
  }

  return nums;
};

# Working Example

Type yarn test on console to run vitest.

# Practice Problems

LeetCode 147