function insertionSort(arr) {
const a = [...arr];
for (let i = 1; i < a.length; i++) {
const key = a[i]; let j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
return a;
}Insertion sort builds the sorted array one element at a time by shifting larger values.
Insertion Sort builds the sorted array one item at a time. It iterates through the array, and for each element, finds the correct position in the sorted portion and inserts it there.
Time Complexity: O(n²) worst case, O(n) best case Space Complexity: O(1)
function insertionSort(arr: number[]): number[] {
// Implement insertion sort
// Insert each element into its correct position
}
insertionSort([64, 34, 25, 12, 22]) // [12, 22, 25, 34, 64]