>Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays.

Oh, no. You shouldn't split list by calculating length.

Try this instead:

   even (x:_:xs) = x : even xs
   even xs = xs
   odd = even . drop 1

   splitList xs = (even xs, odd xs)

Voila! Completely lazy, O(1).

So for merge. See here: http://lambda-the-ultimate.org/node/608?from=0&comments_... The solution contains proper merge algorithm.

And yes, I never read Okasaki in full. But, I use Haskell semi-professionally from 1999 and professionally from 2006.