Insertion

Insertion Sort is also another simple sorting algorithm that works by iteratively inserting each element of an array into its correct position within a sorted subarray.

Here are the basic steps of the Insertion Sort algorithm:

1. Starting with the second element in the array, iterate through the unsorted portion of the array.

2. For each element, compare it to the elements in the sorted portion of the array and insert it into the correct position.

3. Repeat step 2 for all remaining elements in the unsorted portion of the array until the entire array is sorted.

Insertion Sort has a time complexity of O(n^2), making it relatively slow for large datasets.

However, it is efficient for sorting small datasets and is often used as a building block for more complex sorting algorithms.

Additionally, Insertion Sort has a relatively low space complexity, making it useful in situations where memory usage is a concern.

pseudocode:

InsertionSort(A)
    for i from 1 to length(A) - 1
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function InsertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
  }

console.log(InsertionSort(numbers));

Output

PS D:\Coding Playground> node playground2.js
[
    0,  1,  2,  4,  5, 6, 44, 63, 87, 99, 283
]