If you're French and of my age (or older) you might remember this weird ad:

"Eat the banana from both ends" it says. How inspiring.

The previous log Has anybody... introduced an idea that remineded me the ad, and then I had doubts.

But now I am confindent and the doubt is gone because I formalised the problem, and it was simple. The key is that the data must have only one way to be sorted, which is the case usually, right ?

If there is only one way to sort the data, then there is one way to sort it from the "higher values" as well as from the "lower values". In this case, both sorts can proceed by giving each parallel sub-task exactly one half of the data to process.

Again it's one of those things that sound so obvious when you find them, yet you can't find any reference in the open litterature. According to Knuth (through Wikipedia), merge sort was invented in 1945 by John von Neumann so at least someone should have thought about merging both ends at the same time in 77 years...