Simple destructive quicksort

Programming languages have become more expressive over time. Consider quicksort. Hoare's original version was quite difficult to understand - IIRC it wasn't even recursive. Nowadays the two-line quicksort is an icon of Haskell:

qs [] = []
qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (>= x) xs)

Unfortunately it's also an icon of unrealistic examples - it makes too many passes over the lists, and conses far too much, so it isn't all that quick. The more efficient sorts don't make such impressive examples - especially the destructive ones, whose Haskell incarnations are infested with intimidating monads.

Here's a gem from the Pitmanual: a reasonably clear destructive quicksort in fifteen lines.

Date: 9 September 1981 18:44-EDT
From: George J. Carrette <GJC>
To:   KMP
cc:   JAR

I think that the QUICKSORT properly coded is even shorter and neater than
the BUBBLESORT. It is also better for showing students since it is
naturally recursive, divide&conquer.

(defmacro rplacd&pop (x &optional y)
  `(rplacd (prog1 ,x (setq ,x (cdr ,x))) ,y))

(defun quicksort (list judge)
  (if (null list)
      ()
      (do ((proof (rplacd&pop list))
           (goats ())
           (sheep ()))
          ((null list)
           (nconc (quicksort goats judge)
                  proof
                  (quicksort sheep judge)))
        (if (funcall judge (car list) (car proof))
            (setq goats (rplacd&pop list goats))
            (setq sheep (rplacd&pop list sheep))))))

rplacd&pop captures the idea of destructively removing the first element of a list. It sounds like a nice example, since it uses a macro to express a by-reference operation in a language without by-reference parameters. But it's not really good for showing students, because it's not safe - it evaluates x twice and its subforms (if any) thrice. (Update 6 April: it uses setq, not setf, so it's ok in Maclisp, because it only works on variables. Even in Common Lisp it would only be a problem when used with a symbol-macro.) I don't know how to do it right in Maclisp, but in Common Lisp it requires the sort of macrology that inspires fear and loathing:

(defmacro rplacd&pop (x &optional y &environment e)
  (multiple-value-bind (temps forms svars writeform readform)
                       (get-setf-expansion x e)
    `(let* (,@(mapcar #'list temps forms)
            (,(car svars) (cdr ,readform)))
      (prog1 ,readform
        (setf (cdr ,readform) ,y)
        ,writeform))))

This might be a good example of how to write setf-like macros, which is a confusing corner of Common Lisp that certainly deserves some examples. But it's no way to write a clear quicksort!

Of course, the simplest way for a language to make a realistic quicksort simple is to predefine partition. Is that cheating? I think it could be useful often enough to belong in a standard library. But to truly simplify quicksort down to a one-liner will require some advances in expressiveness, so we can write something closer to the natural definition: partition on the first element and recurse on both halves.