Given an integer array nums, sort it in non-decreasing order using the recursive form of Insertion Sort. First recursively sort the first n-1 elements, then insert the last element (nums[n-1]) into its correct position among the already sorted prefix. Return the sorted array.
Input: An integer array nums.
Output: Return the sorted array as [v1,v2,...].
Input: [5,1,4,2,3]
Output: [1,2,3,4,5]
Explanation: Sort [5,1,4,2] -> [1,2,4,5], then insert 3 -> [1,2,3,4,5].Input: [2,1]
Output: [1,2]
Explanation: Sort [2] -> [2], insert 1 at front -> [1,2].Input: [1,2,3]
Output: [1,2,3]
Explanation: Already sorted; each insertion is a no-op.1 <= nums.length <= 100-10^9 <= nums[i] <= 10^9