FUNCTIONAL PEARL On merging and selection

Abstract

Given two ascending lists xs and ys of combined length greater than n, consider the computation of

formula here

The standard function merge merges two ascending sequences and (!!) denotes list indexing. With a lazy evaluator the computation takes O(n) steps; with an eager one it takes O(p+q) steps, where p=length xs and q=length ys. Now in functional programming it is more efficient to index a tree than a list, so the question arises: can we find a faster solution if xs and ys are each represented by a tree? Somewhat surprisingly the answer is yes: if xs and ys are each represented by balanced binary search trees, then the computation can be reduced to O(log p+log q) steps. This is despite the fact that there is no known method for merging two binary search trees in better than linear time. The details, presented below, depend on a subtle relationship between merging and indexing.