# Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library offers a stable sort via a list-based merge sort, and an unstable sort using a binary heap. I was thinking about whether it would be possible to write an efficient incremental sort, allowing early and late elements to be accessed before sorting the middle. Here is an inefficient way:

Use the replicate :: Int -> a -> Seq a function to lay out the desired structure of the result sequence. This is an incremental logarithmic operation, so not expensive enough to worry about. Use the replicated structure to find the order statistics corresponding to successive Digit boundaries. Use median-of-medians to select those statistics from the sequence. Partitioning the sequence into digits should then take $O(n\log n)$ time, incrementally. The actual digits and the 2-3 trees within can be formed using median-of-medians to find the appropriate order statistics ($\tfrac13s$ and $\tfrac23s$, etc.) and partition along them. This should give access to the $i$th element in no more than $O(n\log(\min\{i+2,n-i+1\}))$ time (perhaps better?), and the total sorting time should be $O(n\log n)$.

Unfortunately, the constant factors are likely to be awful, because median-of-medians has a reputation for sluggishness. What I was wondering is whether it might be possible to use approximate medians instead of exact ones to speed things up. In particular, breaking up the sequence into groups of five and taking the median of the medians produces a value in the middle $\tfrac4{10}$ of the sequence. While 2-3 trees are not the most flexible structures in the world, it seems possible that by intentionally using "poorly balanced" trees, with many 2-nodes and few 3-nodes, I could get enough wiggle room to use approximate medians for partitioning. Is this possible? If so, how might it be done?

### Edit

I am now looking into an alternative approach, loosely based on ideas I encountered in Optimal Incremental Sorting by Paredes and Navarro. As they describe, selection (by QuickSelect or median-of-medians) partially sorts the elements of the sequence, partitioning them into segments below and above each chosen pivot. They keep the segment boundaries in a stack to take advantage of this. For my purposes, a stack is insufficient, but I think I can use a finger tree of segments that lets me quickly find a required segment, split the sequence around it, and then, once that segment has been subdivided, to append the pieces to either side as appropriate.

newtype Seq a = FingerTree (Elem a)
data FingerTree a = Empty
| Single a
| Deep !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
data Digit a = One a
| Two a a
| Three a a a
| Four a a a a
newtype Elem a = Elem a
data Node a = Node2 !Int a a
| Node3 !Int a a a

• Since you tag with quicksort, are you familiar with its variants? Sacrificing worst-case linearithmic asymptotic runtime for average-case efficiency in practice is ... standard. Median-of-three is one example, and hard to beat (iirc). – Raphael Mar 15 '15 at 20:04
• @Raphael, there are various ways to get approximate order statistics. The question is whether it's possible to use them in this particular context. If not, then it might be reasonable to use something like median-of-three quickselect, but such "Las Vegas" algorithms tend to be a bit awkward in a purely functional context—I/O is required to obtain a random seed. – dfeuer Mar 15 '15 at 20:42
• @Raphael, the point is that to accomplish an incremental sort for this data structure, I need to be able to partition into structures of sufficiently appropriate sizes. I don't know if I have enough flexibility to do that with an approximate order statistic. The flex comes, essentially, from the fact that a 2-3 tree of depth $d$ can have anywhere from $2^d$ to $3^d$ leaves, so there are, in all but a few cases, many ways to partition the sequence that will work. But arranging to be sure of that, and actually accomplishing it, seem rather tricky. – dfeuer Mar 16 '15 at 1:58
• I seem to have misread your question a bit, sorry. (Why's quicksort there?) I have not thought about your problem in depth, but it seems obvious that you can't make sure you have a good partitioning with approximate/heuristic order statistics, but you may very well have one on average. If your algorithm works with any partitioning, "all" you need is an average case analysis (or, failing that, experiments). – Raphael Mar 16 '15 at 7:22
• @Raphael, I tagged it quicksort because it seemed sufficiently quicksort-like in its general flavor, but I changed it to sorting to avoid any further confusion. The point is that approximate order statistics can be given definite bounds. Are those bounds tight enough for incremental top-down finger tree construction? I don't know. – dfeuer Mar 16 '15 at 14:00