2 votes 2 votes Two unsorted arrays of size m and n are to be sorted into a single array, what is best case time complexity? Algorithms algorithms sorting time-complexity + – Pradatt Sharma asked Nov 20, 2017 retagged Jun 30, 2022 by makhdoom ghaya Pradatt Sharma 905 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Pradatt Sharma commented Nov 20, 2017 reply Follow Share And why not like this If we sort first array, mlogm For second, nlogn And after that we can take two sorted arrays and apply merge sort, that will take O(m+n) So total, O(mlogm+nlogn+m+n) = klogk, k=max(m, n) Isn't this approach right? 0 votes 0 votes abhishek tiwary commented Nov 20, 2017 reply Follow Share @shrma read your 4th line 0 votes 0 votes Pradatt Sharma commented Nov 20, 2017 i edited by Pradatt Sharma Nov 20, 2017 reply Follow Share Yes got it buddy, since mlogm and nlogn are of same order, so can't ignore one. Correct? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes First sort both arrays and then combined into a single array, complexity = m log(m) + n log(n) + (m+n) First combine into a single array and then sort the combined array, complexity = (m+n) log (m+n) suraj answered Nov 20, 2017 suraj comment Share Follow See all 3 Comments See all 3 3 Comments reply srestha commented Nov 20, 2017 reply Follow Share Combine in a single array done by heapification? 0 votes 0 votes rajatmyname commented Mar 15, 2018 reply Follow Share @suraj in the first line it should be nlog(n) 1 votes 1 votes suraj commented Mar 16, 2018 reply Follow Share Thanks. Corrected now. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Simply combine both arrays then resultant array will have m+n elements. Then apply best sort method on O(nlogn) which will give here (m+n)log(m+n) So here by combining and then sorting is efficient. Ashwin Kulkarni answered Nov 20, 2017 Ashwin Kulkarni comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes We can sort both arrays using Linear sort and Linear sort take O(n+k) time and after sorting them we can merge them into one array. For merging O(n) time taken so total time complexity will be:- 2.(O(N+k)) (sorting) + O(n)(for merging) so it is some how equal to O(n). ravi kant Gautam answered Apr 22, 2018 ravi kant Gautam comment Share Follow See all 0 reply Please log in or register to add a comment.