# Merge sort with recursion depth optimization. What does O(n*lg(n/k)) mean?

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?

### b)

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?

• k is an exact number for which we start using insertion sort instead of merge sort doesn't explicitly state two things: number of what and use insertion sort below or above - in contrast to the quote: sublists of length k are sorted using insertion sort: how many?. Jul 1 at 7:22