Implement insertion sort to sort an integer array in ascending order. Treat the first element as a sorted prefix of size one. For each subsequent element, save it as the key, then walk leftward through the sorted prefix, shifting any larger elements one position to the right. Drop the key into the gap that opens up. Repeat until every element has been inserted.
Return a new sorted array; do not mutate the input.
Input
arr: an array of integers (may be empty)
Output
A new array containing the same integers sorted in ascending order.
Examples
Example 1
Inputarr = [5, 2, 4, 6, 1, 3]
Output[1, 2, 3, 4, 5, 6]
Explanation: Each new element is inserted into its correct slot within the growing sorted prefix.
Example 2
Inputarr = [12, 11, 13, 5, 6]
Output[5, 6, 11, 12, 13]
Explanation: 11 slides before 12, 13 stays put, then 5 and 6 each shift the larger values right.
Constraints
0 <= arr.length
Elements are integers.
The input array must not be mutated.
Use the insertion sort algorithm.