2-way bottom-up merge sort the last level (except original array) named as level-1, so on... and let n=2k ===> only k levels present totally
if two sorted arrays have n1 and n2 elements ===> to merge them we require no.of comparissions
1) minimum = n1
2) maximum = n1+n2-1
minimum no.of comparissions required for forming
level 1 :- n21n21 . 1
level 2 :- n22n22 . 2
level 3 :- n23n23 . 4
.
.
.
.
level j :- n2jn2j . 2 j-1
Total Comparissions = ∑kj=1n2j.2j−1∑j=1kn2j.2j−1 = ∑kj=1n2∑j=1kn2 = n2∑kj=11n2∑j=1k1 = n2(k)n2(k) = n.log(n)2