On Jul 8, 2006, at 22:41, Dark A. wrote:

Stuart

[James’ code below]

First, the formal to the recursive_sort method are an unsorted array

(named ‘unsorted’), and an array that’s in sorted order (named

‘sorted’).

The call in sort uses actual parameters of the array being sorted

(‘array’) and an empty array (that’s what [] means). An empty array

is in sorted order by definition.

So, starting off with an empty sorted array, recursive_sort finds the

*lowest* element (not the first element) in the unsorted array, adds

it to the sorted array, and removes it from the unsorted array.

At this point, the method has a sorted array with one element, and an

unsorted array where every element is >= everything in the sorted

array (since we took out the lowest element).

The key thing to note here is that these two arrays are exactly the

sort of thing you could pass into recursive_sort: an unsorted array,

and a sorted array.

So that’s exactly what we do, pass those two arrays as the parameters

to another call of recursive_sort. The next call has one small

wrinkle, are we *sure* that when we move the lowest element from the

unsorted array to the sorted array, that the sorted array is still

sorted?

The answer’s yes, because in the first call, we moved the lowest

element. In the second call, we’re moving the next-lowest element,

and we’re using ‘push’ to put it on the end of the list. So, we’re

going to pushing the lowest, then the next-lowest, then the next-next-

lowest, and so on, and that ensure that the sorted array is always in

sorted order. This is basically the same strategy you used before in

your loop, just done using recursion.

Here’s a walk-through of the array values for each call for James’

example:

```
-- unsorted array -- sorted array
```

- – [‘zeta’, ‘beta’, ‘alpha’, ‘beta’] – []
- – [‘zeta’, ‘beta’, ‘beta’] – [‘alpha’]
- – [‘zeta’, ‘beta’] – [‘alpha’, ‘beta’]
- – [‘zeta’] – [‘alpha’, ‘beta’, ‘beta’]

0 is the parameters from the first call to #recursive_sort made from

#sort. 1 is the parameters to the next call of recursive_sort (which

is made inside the first call). 2 is the parameters to the next call

of recursive_sort, and so on.

When you get to 3, though, things are a little different. The method

finds the lowest element in the sorted array (‘zeta’ at this point),

does the push, and creates a new unsorted list, they’ll look like this:

new_unsorted: []

sorted: [‘alpha’, ‘beta’, ‘beta’, ‘zeta’]

If you look at the if statemetn at the bottom of the method, you’ll

see that rather than making another call to recursive_sort, when the

new_unsorted list is empty the method returns the sorted array.

Note that this is the first value returned in any of the calls so far!

It’s important to remember when you’re debugging recursive methods

that they generally consist of a large chain of method calls until

some termination condition is met, followed by a large chain of

returns. In this case, the calls and returns are structured

something like this:

call #0 asks for the result of call #1

call #1 asks for the result of call #2

call #2 asks for the result of call #3

call #3 returns a result: the sorted array

call #2 returns the result of call #3

call #1 returns the result of call #2

call #0 returns the result of call #1

And you end up with the sorted array.

Hope that helps a bit,

matthew smillie.