Insertion Sort

Implement insertionSort(array) — sort an array of numbers ascending using insertion sort. The idea is the one you use without thinking when you pick up a hand of playing cards: you keep the cards in your hand sorted, and each new card you draw slides left past the bigger cards until it sits in the right place. You grow a sorted region one element at a time, inserting each new element where it belongs.

Signature

// array: number[]   — the numbers to sort. Treated as read-only.
// returns: number[]  — a NEW array with the same numbers in ascending order.
//                      The input is not mutated.
function insertionSort(array: number[]): number[];

Examples

insertionSort([3, 1, 2]);
// → [1, 2, 3]

insertionSort([2, 2, 1]);
// → [1, 2, 2]

Notes

• Return a new array. Sort a copy; the caller's array must come back unchanged. A test checks that the input is not mutated and that the returned reference is not the input.
• Numeric order, not string order. [10, 2] sorts to [2, 10], not [10, 2]. Compare the numbers directly — don't lean on the default Array.prototype.sort, which compares as strings.
• Handle the edges. Empty array returns []; a single element returns itself; an already-sorted array comes back in the same order; duplicates and negative numbers all work.
• Implement the algorithm yourself. The point is the insertion-sort loop, not calling .sort().