Quick Sort in Common Lisp

After watching some of Tim Roughgarden’s videos on sorting algorithms, I thought I’d post an implementation of quick sort in Common Lisp as an example of a sorting algorithm implemented in CL. It’s a simple enough example(at < 20 LOC) that demonstrates one non-imperative approach to algorithm implementation. The complete code can be found here.

(defun quick-sort-generic2 (sequence cfun &optional result-type)
  (if (<= (length sequence) 1)
      (copy-seq sequence)
      (flet ((partition (fun array)
           (list (remove-if-not fun array) (remove-if fun array))))
    (let* ((result-type (or result-type 'vector))
           (pivot-ind (random (length sequence)))
           (pivot-val (elt sequence pivot-ind))
           (rem-seq
        (remove pivot-val sequence :start pivot-ind :end (+ 1 pivot-ind)))
           (part (partition (lambda (x)
                  (apply cfun (list x pivot-val))) rem-seq)))
      (concatenate result-type
               (quick-sort-generic2 (car part) cfun result-type)
               (list pivot-val)
               (quick-sort-generic2 (cadr part) cfun result-type))))))
* (test-sort)
started quick-sort (generic, array) ...
Evaluation took:
  0.089 seconds of real time
  0.081912 seconds of total run time (0.081587 user, 0.000325 system)
  92.13% CPU
  142,664,472 processor cycles
  8,375,024 bytes consed
quick-sorted 10000 items (first 10 shown) :
#(9998 9998 9998 9997 9997 9996 9995 9994 9993 9992)
started quick-sort (generic, list) ...
Evaluation took:
  0.062 seconds of real time
  0.058722 seconds of total run time (0.058417 user, 0.000305 system)
  95.16% CPU
  99,419,648 processor cycles
  9,371,456 bytes consed
quick-sorted 10000 items (first 10 shown) :
(9999 9998 9997 9997 9996 9996 9994 9993 9993 9992)