What do we understand about Insertion Sort?
- It uses 2 loops (outer for-loop & inner while-loop) and 2 pointers
- 1st pointer starts from 1 item after the 2nd pointer
- 2nd pointer starts from 1 item before 1st pointer
- 2nd loop loops decrementally till 0
- as long as current value is more than left side value we copy the left side over to current
- insertion happens after the 2nd loop is finished
- Mutation is performed on the original Array
- Time complexity
- Best -> O(n)
- Average -> O(n^2)
- Worst -> O(n^2)
- Space complexity
- O(1)
function InsertionSort(arr) {
for (let i = 1; i < arr.length ; i++) {
let currentValue = arr[i];
let oneIndexBefore = i - 1;
while (oneIndexBefore >= 0 && arr[oneIndexBefore] > currentValue) {
arr[oneIndexBefore + 1] = arr[oneIndexBefore];
oneIndexBefore--;
}
arr[oneIndexBefore + 1] = currentValue;
}
return arr;
}
Top comments (0)