URL: http://coldattic.info/shvedsky/pro/blogs/a-foo-walks-into-a-bar/posts/49

I used to think that the "merge" step of merge sort cannot be efficiently parallelized, because the fact that an element belongs to the tail of one sorted array could not even guarrantee that it won't rank first in the other sorted arrary.

But this article illustrates that we can get across this obstacle by doing some binary search in advence.

And even better, this algorithm preserves merges sort's ability to be a external sort.