Give an array of integers ```nums``` and number of sorted subarrays ```S``` in the array, sort the array.\n\nFor example:\nnums = [2, 6, 8, 4, 5, 9,1, 3, 7], S= 3\n\nExplanation: Given array has 3 subarrays, which are sorted, namely {2, 6, 8}, {4, 5, 9}, and {1, 3, 7}, you job is to sort the array.\n\nAnswer: [1, 2, 3, 4, 5, 6, 7, 8, 9]\n\nAssumptions:\n1. Input ```S``` is always right, note that you can calculate it yourself as well.\n\nNote: Obviously you algorith should do better than O(NlogN), otherwise we could just use one of the comparison based sorting algorithm.\n\n

Give an array of integers nums and number of sorted subarrays S in the array, sort the array.\n\nFor example:\nnums = [2, 6, 8, 4, 5, 9,1, 3, 7], S= 3\n\nExplan