Suppose we have a list of numbers like this:

What we want is a list of the same numbers, in ascending order:

(There's no reason the items have to be numbers, as long as we have some way to order them, like the < operator for numbers. But numbers are easiest to talk about in this context.)

There are many different sorting algorithms. But the best one for recursively generated lists, and probably the most elegant, is called mergesort. Here's the idea in a nutshell: Divide the list in half; recursively sort each half; then merge the two sorted sublists. The base case is an empty list or a one-item list because the list is already sorted.

To get started, let's go over one way to divide lists in half. We'll refer to this as the split-in-half problem. The easiest way to solve the split-in-half problem turns out to be putting the odd-indexed items (first, third, fifth, etc.) in one half and the even-indexed items (second, fourth, sixth, etc.) in the other.

Note: this will not return the numbers whose values are even/odd, but those whose positions are even/odd. For example, evens((5, 6, 2, 4, 3, 9)) will report (6, 4, 9) and not (6, 2, 4).

All the work here, basically, is done by the in odd numbered items. This skips the second item and makes the recursive call on items 3 through the end of the list. Note that even numbered items is not directly recursive; it calls odd numbered items, not itself.

Here is a Snap! file OddEven that may be useful in answering these questions.

☞ Why does odd numbered items need two base cases?

☞ Write a version of even numbered items that calls itself recursively instead of using odd numbered items.

☞ Can you write a version of odd numbered items that uses (the original) even numbered items instead of calling itself recursively? That structure (A calls B, B calls A) is called mutual recursion.