Processing time of InsertionSort is c n2. To merge k pre-sorted subarrays that contain together n items you have to compare the k top items in all the sub- arrays to choose the current maximum item and place it into the sorted array (assuming that all the items have to be sorted in ascending order). Therefore, the time for merging is proportional to (k 1) n.

Let the processing time of the merge be c (k 1) n where the scale factor has the same value as for InsertionSort. Analyse whether it is possible to accelerate sorting of n items in the following way:

-Split the initial array of size n into k subarrays of size n/k. The last subarray may be longer to preserve the total number of items n but do not go in such details in your analysis.

-Sort each subarray separately by InsertionSort.

-Merge the sorted subarrays into a final sorted array.

If you have found that the acceleration is possible, then find the optimum value of k and compare the resulting time complexity of this sorting algorithm to that of InsertionSort and MergeSort.