Insertion Sort

Given an integer array nums, sort it in ascending order using insertion sort and return the array. Insertion sort grows a sorted prefix from left to right.…

Given an integer array `nums`, sort it in ascending order using insertion sort and return the array. Insertion sort grows a sorted prefix from left to right. For each next value, shift every larger prefix value one position to the right, then place the value into the gap that remains.

- `1 <= nums.length <= 10^3` - `-10^6 <= nums[i] <= 10^6` - Values may repeat. - Do not use a built-in sorting function.

Example 1: input nums = [12,11,13,5,6]; output [5,6,11,12,13]. Each value is inserted into the sorted prefix; 5 and 6 shift several larger values.

Example 2: input nums = [1,2,3]; output [1,2,3]. Every value already belongs after the prefix, so no shifts are needed.

Example 3: input nums = [3,1,3,2,1]; output [1,1,2,3,3]. Equal values retain their order because only larger values shift.

Category: Sorting. Topic: sorting-searching. Difficulty: Easy. Patterns: linear-scan, sorting.