Can we make Data.Sequence.sort incremental and/or faster?

I admit that this idea is most likely insane, but there are a few vague ideas running around in my head and I figured I might as well get them out in the open in case they inspire someone.
1. Getting the first few and the last few elements can be done in O(n), and that's enough to build the first level of a finger tree.
2. Frederickson's heap selection algorithm theoretically lets us find a "block" of k smallest/largest elements in a binary heap, represented as an array, in O(k) time. This will only help, I believe, if we can then get the next 2k or 3k or so elements quickly, which may well be impossible.
3. Median-of-medians finds the median of the medians of groups of 5 elements each, producing an element in the middle 40%. Can we use such approximate medians to partition a sequence portion repeatedly, forming a 2-3 tree? It's possible, of course, to get exact medians, but the constant factors for that are very bad.