# More on Merging and Selection

*Jeremy Gibbons*

### Abstract

In his paper *On Merging and Selection* (*Journal of Functional Programming* 7(3), 1997), Bird considers the problem of computing the nth element of the list resulting from merging the two sorted lists x and y. Representing x and y by trees, Bird derives an algorithm for the problem taking time proportional to the sum of their depths. Bird's derivation is more complicated than necessary. By the simple tactic of delaying a design decision (in this case, the decision to represent the lists as trees) as long as possible, we obtain a much simpler solution.

Institution

School of Computing and Mathematical Sciences‚ Oxford Brookes University

Month

oct

Number

CMS−TR−97−08

Year

1997