Amazon Interview Question Software Engineer / Developers
Country: India
then by the similar way, for n-way merge sort it would be nlogn (base n) means O(n), right?
same doubt as oni;
n-way merge sort -> nlogn (base n) which is O(n) + O(n)-> this for merge step which will result in linear time O(n) time for the mergesort right.
As for k-way merge, O(nlogn (base k))
it does not work that way, if u n-way merge, the there is no divide so it takes O(1), but u have to sort the entire array, if u use insertion sort for that sort, its O(n-square),
- both 3 way merge and 2 way merge, they might be O(n logn) base3 and base 2 respectively but former has a larger constant infront of it, as it grows to n it becomes O(n *n * 1)
Don't get confused by the log base 3. O(nlog_3(n)) is equal to O(nlog_2(n)/log_2(3)) = O(nlog_2(n)) since log_2(3) is a constant. Thus, the 3 way merge sort isn't faster than the traditional mergesort.
@oni : nope in n way merge sortt it will not become O(n) because the merging algo then will not take O(n) like previous .
I agree with @geeks .. in 2 way merge sort..in the merging process there are n comparisons and each comparison we compare 2 elements -> n * O(1) = O(n)
in 3 way merge sort , there will be n comparison and each time we compare 3 elements
-> n * O(2) = O(n)
and if k = n, the merging process will be O(n^2) . cos you compare n elements , n-1 elements and so on.
It will still be O(nlogn) to the base 2. The reason being, we can represent a 3 way merge sort by T(n) = 3*T(n/3)+O(n). Applying masters theorm yeilds O(nlogn).
If the complexity would have been really decreasing, then why would have people stopped at 2, or 3? They could have gone for higher values on n then.
for normal merge sort, recurrence relation comes as t(n)=2t(n/2)+ c.n. 1..... bcoz in merge function per iteration compulsory only one comparison is required ..
in case of 3 way merge ... we require 2 comparisons per iteration hence t(n)=2t(n/2)+ c.n. 2= n + 2.c.n. log n (base 3)...eq(1) where as in 2-way merge t(n)=2t(n/2)+ c.n. 2= n + 1.c.n. log n (base 2)...eq(2)
for some same c , put n= 512 eq (1) gives t(n)= 512 + 2.c.512.log 512 (base 3) =512+5814.64 * c eq (2) gives t(n)= 512 + 1.c.512.log 512 (base 2) =512+4608 * c hence 3 way merge is not better.
i hope this may resolve issue. please correct if mistaken Thanks
What about this question?
Rather than separate T[1…m] into two half size arrays for the purpose of merge sorting, we
might choose to separate it into three arrays of size x%3, (x+1)%3, and (x+2)%3, to sort each of
these recursively, and them to merge the three sorted arrays. Give a more formal description of
this algorithm and analyze its execution time. Justify your answer with example.
it will be nlog(n), only base of log will change from 2 to 3.
- abhishekatuw March 15, 2012