0 votes 0 votes shweta sah asked Jun 20, 2018 shweta sah 301 views answer comment Share Follow See 1 comment See all 1 1 comment reply Neeraj Chandrakar commented Jun 20, 2018 reply Follow Share Sorting $m/k$ sublist using insertion sort will take $m/k* O(k^2) = mk$ and for merging 2 list into single list upto height $h$ and each level has total $m$=$(m/k (sublist) * k (elements))$ elements. $ 2^h * k =m$ hence $ h =\log(m/ k)$ and no of elements at each level is $ m $ and height is $\log(m/ k)$ Hence total time for merging is $ m*\log(m/ k) $ total time complexity $ m*k+m*\log(m/ k)$ 0 votes 0 votes Please log in or register to add a comment.