On Jul 8, 2006, at 22:41, Dark A. wrote:
[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
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
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’
-- 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:
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,