Insertion Sort
Implement insertionSort
Given an array of integers, sort it in non-decreasing order using **Insertion Sort** — build up a sorted prefix one element at a time, inserting each new element into its correct position within that prefix.
Insertion sort mirrors how most people sort a hand of playing cards: cards already in hand stay in order, and each new card drawn gets slotted into the right spot among them. It's not the fastest general-purpose sort, but on nearly-sorted data it does very little work, and it needs no extra memory.
Example 1:
Input: arr = [7,2,9,4,2,8]
Output: [2,2,4,7,8,9]
Example 2:
Input: arr = []
Output: []
Example 3:
Input: arr = [5]
Output: [5]
+ 5 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ arr.length ≤ 200 - ●
-1000 ≤ arr[i] ≤ 1000 - ●
Sort in non-decreasing order
arr =
[7, 2, 9, 4, 2, 8]