18
for class on Thursday April 6, 2000
Please read Sections 7.9 and 7.10 of the Schneider and Gersting text (we're postponing 7.8), and be prepared to discuss the following:
Sorting again. Try to wrap your head around this idea: a sort function might call itself on some smaller portion or portions of the array to be sorted. "But but but" (I hear you cry) "...how can that work? Isn't that like a circular definition?" Well here's one way to do this: you can sort an array by first sorting the left half, then the right half, and then merging the two sorted halves. Of course if the array has size 1 you're already done and can return. The tricky part is this: when you go to sort the left half, you use this very same function, and sort the left half's own left half and right half and merge those. The underlying idea here is a powerful (and, for novices, usually difficult) tool known as recursion.