Algorithm analysis

848 Views Asked by At

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? Why?

Wouldn't this depend on the threshold, or is there another way to look at this?

1

There are 1 best solutions below

1
On BEST ANSWER

How do you get $n$ merge sorts?

  1. You call it once for the whole list. You get two lists.
  2. You call it twice (once for each of lists from the previous step). You get four lists.
  3. You call it four times...

So, the total is

$$1 + 2 + 4 + 8 + \cdots = \sum_{k=0}^m 2^k = 2^{m+1} - 1.$$

Now, how many final calls (those that call some other sort, in your case insertion) do you have? That's the last summand above: $2^m$. So, you call insertion sort $2^m$ times, given that your merge sort was called $n = 2^{m+1} - 1$ times. Or, in terms of $n$, you have $(n+1)/2$ calls to the insertion sort.

For $n$ that is not of the form $2^{m+1} - 1$, i.e., $2^{m+1} - 1 < n < 2^{m+2} - 1$ for some $m$, you'll have a disbalance in the calls in the last level (assuming you're doing everything as balanced as possible). So, you got $2^m$ lists from the $(m-1)$-st step and you have called merge sort $2^{m+1}-1$ times. You still have

$$n' = n - 2^{m+1} + 1, \quad m = \lfloor \log_2 (n+1) \rfloor - 1,$$

calls to merge sort, each producing $2$ lists from $1$. So, you get

$$2n' + (2^m - n') = n - 2^m + 1$$

lists and, hence, as many calls to the insertion sort. This is a generalization of the $n = 2^{m+1} - 1$ case.

The threshold, given that it is a constant number of calls, will affect the length of these mini-lists, not the number of calls. If the threshold is given in terms of the length of the list that is being sorted with insertion sort, then the above does not apply (but you do get that the number of merge sort calls depends on the length of the list).