Parallel Merge - Intro to Parallel Programming

[rupaksarkar]

Isn't this slower than the normal approach ? You have to iterate over the elements which takes up O(n) right there, then you have to binary search the other array which takes O(logn) in each of the steps. So, the merging of two sorted lists alone becomes a task of O(nlogn). The overall complexity becomes O(nlognlogn) or O(n(logn)^2).