1 votes 1 votes Let there are n elements in array and number of sorted subarray is log n of size n/ log n each then what is the time complexity to sort given array Algorithms sorting time-complexity + – Meenakshi Sharma asked Mar 25, 2017 • retagged Jun 20, 2022 by makhdoom ghaya Meenakshi Sharma 434 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments vijaycs commented Mar 26, 2017 reply Follow Share ^ use mergeing concept of merge sort .. suppose you are given two sorted list .. how would you merge those sorted list into one sorted list ... now use the same concept in more sorted list ..as @dekha told ..two way mege sort ..means take 2 sorted list and merge them into 1 and take another 2 and merge into 1 .. keep doing it in hierarchical way .. if you know merge sort well then now you can proceed ... if you want readymade then search in google you will get it ..:p 1 votes 1 votes Devshree Dubey commented Mar 26, 2017 reply Follow Share @vijaycs, if n is infinite, then d process of merging d two list wouldn't stop as u have told.Yeah. However, here it is mentioned dat d merge sort is two way merge sort. 0 votes 0 votes Devshree Dubey commented Mar 26, 2017 reply Follow Share Plz anybody work out d steps of time complexity. :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes Merge procedure takes = $O(m+n)$ time where $m$ and $n$ are sorted subarray sizes Total complexity = (No of levels) * (Each level work) = $n\cdot \log_2 \left ( \log n \right )$ dd answered Mar 26, 2017 • selected May 16, 2017 by Meenakshi Sharma dd comment Share Follow See all 0 reply Please log in or register to add a comment.