Brian Harvey, co-author of our textbook Simply Scheme compared
several sorting methods in a posting to the Usenet comp.edu newsgroup.
Brian writes:
When I'm teaching data structures, in fact, I go ahead and lecture in Scheme no matter what language the students are using. There is something really appealing about filling four chalkboards with
(define (insertion-sort stuff)
(if (null? stuff)
'()
(insert (car stuff)
(insertion-sort (cdr stuff)))))
(define (selection-sort stuff)
(if (null? stuff)
'()
(cons (smallest stuff)
(selection-sort (remove (smallest stuff) stuff)))))
(define (mergesort stuff)
(if (< (length stuff) 2)
stuff
(merge (mergesort (one-half stuff))
(mergesort (other-half stuff)))))
(define (partition-sort stuff)
(if (< (length stuff) 2)
stuff
(let ((pivot (guess-median stuff)))
(append (partition-sort (filter (lambda (x) (< x pivot)) stuff))
(filter (lambda (x) (= x pivot)))
(partition-sort (filter (lambda (x) (> x pivot)) stuff))))))
Only imagine that the last two are in a column next to the first two.
Then I can say "the first column (insertion-sort and
selection-sort) takes things one at a time, the second
column (mergesort and partition-sort) takes
things half at a time. The first row (insertion-sort and
mergesort) divides arbitrarily and does the sorting in
the recombination; the second row (selection-sort and
partition-sort) sorts in the division, then just
recombines the results by concatenation."
(Brian Harvey's comments reproduced here with his permission.)