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)
```