In the insertion sort n element sorted time in the worst case is O(n2) time. In the problem k length takes O(K2) time .Hence
N/K sublist takes O(nk) times .
If we merge sorted array using merge procedure it takes nlog(n/k) time .So total time=nk+nlog(n/k) time
Proof
An insertion sort , to sort an array of k elements will take O(k^2) time complexity.
There are m/k such sublists , so to sort each, time taken will be O(k^2* m/k) = 0(mk)
Merge sort
First understand how merge sort takes nlogn when there are n elements to be sorted.
At each height, merge sort needs n constant comparisons.( If you want proof ask me)
And height of balanced tree is log(n) , and at each height n comparison . Total computations is n*logn
Now , here in the question also as there are total m/k*k=m elements so at each height there will be m comparisons.
But height is not logn here, The number of elements in leaf nodes are not n its m/k as given in question. So , total height will be log(m/k).
Each height m computation , total height log(m/k)
Total computation will be m*log(m/k)
Total Complexity : O(MK) + O(M * LOG(M/K))
