Write a program for the recursive implementation of Insertion Sort.

Example 1

Input: A[] = [5,2,3,1]
Output: [1,2,3,5]

Example 2

Input: A[] = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]