CODEWITHSUNDEEP
algorithmsortingmerge
user8929476
user8929476

Reputation: 37

Insertion sort on small arrays with merge procedure:

Consider the problem:

Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n^2) worstcase time, the constant factors in insertion sort makes it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification for 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.

Question: Show that the sublists can be merged in Θ(n lg(n/k)) worst-case time:

My solution:

To merge n/k sublists into n/2k it takes Θ(n) times

To merge n/2k sublists into n/4k it takes Θ(n) times

...

To merge 2 sublists into 1 it takes Θ(n) times

Then I was struggling with further steps and I had a look at the solution:

We have lg(n/k) such merges, so merging n/k sublists into one list takes Θ(n lg(n/k)) worst-case time.

I have two questions:

1)How do they end up with lg(n/k) merges? Please, clarify the calculations?

2)Why is the final result Θ(n lg(n/k))?

Upvotes: 1

Views: 1606

Answers (1)

ilim
ilim

Reputation: 4547

You seem to be pretty close to the actual answer. I believe the phrasing of the answer you looked up is what makes it harder for you to understand, because I do not think that the total number of individual merges required is lg(n/k). What I believe the answer refers to is the number of merging steps required until we end up with the sorted list.

Instead of the answer, however, let's continue building onto your reasoning. Merging two lists of length k has O(k) time complexity. To merge n/k such lists into n/(2k) lists, we will do n/(2k) merges with complexity O(k) each, resulting in an overall O(n) complexity, as you mentioned.

You may extend this logic to the next step, where n/(2k) lists are merged into n/(4k), and state that the second step has O(n) complexity, as well. In fact, each merging step, will take O(n) time.

The next thing to do here is estimating how many of these merging steps we have. We started with n/k lists, and after the first step we obtained n/(2k) lists. After that, at each step, the number of lists is halved, until there is only 1 list left, which will be our result. (i.e. sorted list) Well, how many times do you think we have to divide n/k by 2, until we end up with 1? That is exactly what log(n/k) means, isn't it? So, there will be log(n/k) of such merging steps, each of which takes O(n).

Consequently, the entire procedure will have a time complexity of O(nlog(n/k)).

Upvotes: 3

Related Questions