I have been reading an excellent book "Introduction to algorithms" and faced an obstacle on set of problems after merge sort chapter (Problem 2.1 - Insertion sort on small arrays in merge sort). You are about to see the whole statement of the problem - you can skip it, if you would like -, then I will ask questions.
Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.
a)As I can guess, variable k is an exact number for which we start using insertion sort instead of merge sort. Ok, but what does n/k mean? Let us suppose, that n = 4 and k = 2, then we have the following recursion tree:
4 # Root. 2 2 # At this level we start using insertion sort. 1 1 1 1 # Leaves.
Having that I still cannot understand what n/k means. How is that relevant to subarrays?
Running time of merge sort with such optimization is O(n*lg(n/k)). What does n mean in the running time of that algorithm? I understand that we spend O(n/k) time to sort one subarray and we have lg(n/k) levels (again, what is n/k?), but why do we multiply all of this by n?