export const insertionSort = (arr = []) => {
for (let i = 0; i < arr.length; i++) {
let val = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > val) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = val;
}
return arr;
};
Algorithm is one of the simplest algo with simple implementation.
Insertion sort is efficient for small data values
Adaptive in nature, ie it is appropriate for data sets which are already partially sorted.
Iterate from arr[1] to arr[N]
Compare the current element (val) to its predecessor.
If val is smaller than its predessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Time Complexity: O(N2) as there are two nested Loops Auxillary Space: O(1)