I think the median of the results works great in any case (but, you are the expert here). If we find the result median in each of the two inputs, say 'a' and 'b' we have four merges (two forward, two reverse):

    [0, ..) w (0, ..)
    (.., a) w (.., b)
    [a, ..) w [b, ..)
    (.., n) w (.., n)

each of which should produce n/4 elements and then meet.

If the array is already sorted then great; that split will just "merge":

    [0, ..) w nothing
    (.., n/2) w nothing
    nothing w [n/2, ..)
    nothing w (.., n)

which should go very fast. Anyhow, possible I'm missing something!