algorithm

Question

Consider bottom- up merge sort working on 'n' elements . Assume n is a power of 2. The minimum number of comparisons in order to get sorted list is

a) n log n/2

b)n log n-n+1

c)n logn

d)n logn +n

Comments

c should be answer i think!

---

No

Answer 1

None of the above

             1,2,3,4            = 2 comparison   Final sorted array

     1,2              3,4       = 2 comparison   2nd level

       1  2  3  4              Individually sorted elements

Minimum comparison is only possible when 1st and last element of either array are smaller then first element of another

so in such as case at each level we will have n/2 comparisons

In general= n/2 * number of levels

= $\frac{n}{2}log_{2}n$

For n=2  only 1 comparison

For n=4 only 4 Comparison and so on

Comments

For minimum you are correct
Maximum would be 17 for n=8
If two array of size m and n then max comparison is always m+n-1
Second last element of either array should be greater then second last of another for maximum

---

why we write n/2??

i understand logn for the levels then why n/2logn??? @Tesla!

---

Consider two sorted arrays 1234, 5678

Isn't minimum number of comparisons one, i.e. when last element of 1st array is greater than first element of 2nd array (if 4 > 5)?

Answer 2

Please see the full derivation of the Formula :

For minimum : n*logn / 2

For maximum: n * (logn - 1) + 1