Insertion sort is a simple sorting algorithm, similar to playing cards. Each time a card is picked up, it is placed in its right position in the players hand. Similarly, in each iteration the element is placed in its position. The iteration continues until the whole array is sorted.Advantages of using insertion sort is, it is fast when the input is nearly sorted.Space requirement is minimal.Efficient for small data sets.
function insertion(arr, n) {
for(let i = 1; i < n; i++) {
for(let j = i; j > 0; j--) {
if(arr[j] < arr[j-1]) {
let temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}else{
break;
}
}
}
return arr;
}
Best Case : Ω (n)
Average Case : θ (n^2)
Worst Case: O (n^2)
O(1)
** where n is the length of the array