0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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?. $\endgroup$
    – greybeard
    Jul 1 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.