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)