9.2. Sorting

This section illustrates a list sorting algorithm based on a simple technique known as merge sorting. The procedure sort defined here accepts two arguments: a predicate and a list. It returns a list containing the elements of the old list sorted according to the predicate. The predicate should be a procedure that expects two arguments and returns #t if its first argument must precede its second in the sorted list and false otherwise. That is, if the predicate is applied to two elements x and y, where x appears after y in the input list, it should return true only if x should appear before y in the output list. If this constraint is met, sort will perform a stable sort; with a stable sort, two elements that are already sorted with respect to each other will appear in the output in the same order in which they appeared in the input. Thus, sorting a list that is already sorted will result in no reordering, even if there are equivalent elements.

 (sort < '(3 4 2 1 2 5)) ⇒ (1 2 2 3 4 5) (sort > '(0.5 1/2)) ⇒ (0.5 1/2) (sort > '(1/2 0.5)) ⇒ (1/2 0.5)) (list->string   (sort char>?         (string->list "coins"))) ⇒ "sonic"

A companion procedure, merge, is also defined by the code. merge accepts a predicate and two sorted lists and returns a merged list in sorted order of the elements of the two lists. With a properly defined predicate, merge is also stable in the sense that an item from the first list will appear before an item from the second list unless it is necessary that the item from the second list appear first.

 (merge char<?        '(#\a #\c)        '(#\b #\c #\d)) ⇒ (#\a #\b #\c #\c #\d) (merge <        '(1/2 2/3 3/4)        '(0.5 0.6 0.7)) ⇒ (1/2 0.5 0.6 2/3 0.7 3/4) (list->string   (merge char>?     (string->list "old")     (string->list "toe"))) ⇒ "tooled"

The merge sorting algorithm is simple and elegant. The input list is split into two approximately equal sublists. These sublists are sorted recursively, yielding two sorted lists. The sorted lists are then merged to form a single sorted list. The base case for the recursion is a list of one element, which is already sorted.

To reduce overhead, the implementation computes the length of the input list once, in sort, rather than at each step of the recursion, in dosort. This also allows dosort to isolate the first half of the list merely by halving the length, saving the cost of allocating a new list containing half of the elements. As a result, ls may contain more than n elements, but only the first n elements are considered part of the list.

 (define sort #f) (define merge #f) (let ()   (define dosort     (lambda (pred? ls n)       (if (= n 1)           (list (car ls))           (let ((i (quotient n 2)))             (domerge pred?                      (dosort pred? ls i)                      (dosort pred? (list-tail ls i) (- n i)))))))   (define domerge     (lambda (pred? l1 l2)       (cond         ((null? l1) l2)         ((null? l2) l1)         ((pred? (car l2) (car l1))          (cons (car l2) (domerge pred? l1 (cdr l2))))         (else (cons (car l1) (domerge pred? (cdr l1) l2))))))   (set! sort     (lambda (pred? l)       (if (null? l) l (dosort pred? l (length l)))))   (set! merge     (lambda (pred? l1 l2)       (domerge pred? l1 l2))))

Exercise 9.2.1.

In dosort, when n is 1, why is (list (car ls)) returned instead of just ls? How much allocation would be saved overall by replacing (list (car ls)) with (if (null? (cdr ls)) ls (list (car ls)))?

Exercise 9.2.2.

How much work is actually saved by not copying the first part of the input list when splitting it in dosort?

Exercise 9.2.3.

All or nearly all allocation could be saved if the algorithm were to work destructively, using set-cdr! to separate and join lists. Write destructive versions sort! and merge! of the sort and merge. Determine the difference between the two sets of procedures in terms of allocation and run time for various inputs.