Write a program for the recursive implementation of Insertion Sort.

Example 1

Input: arr[] = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: The output is the sorted array.

Example 2

Input: arr[] = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: The output is the sorted array.