does not seem possible, there is a proof that shows that comparison based algorithm can have at best O(nlogn) worst case running time. You can check this proof from algorithms CLRS book.
Using this proof, by master's theorem if the merge operation can be implemented in O(lgn) using merge sort with this merge operation, the complexity would be O(logn) contradicting with O(nlogn). So I think its not possible to design such merge algorithm. On Nov 8, 4:58 am, lichenga2404 <lichenga2...@gmail.com> wrote: > Suppose we'd like to implement a sorting variant where every element > is compared only a small number of times. > a) devise a divide and conquer algorithm to merge 2 sorted arrays of > length n , which guarantees that every element is included in at most > O(log n ) comparisons. > b) using this modified merge , prove that Merge-Sort will include > element in at most O( (log n)^2) comparisons. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
