Quicksort ain't shit

The fact that it's a commonly taught sorting algorithm is just an accident of history and imperative languages' being popular. It's actually quite a lot more complex than merge sort or heap sort and it's much harder to analyze. (Proving that merge sort runs in O(n log n) is relatively easy; proving that quicksort runs in O(n log n) in expectation is quite hard.)

(defun my-quicksort (L pred)
(if (null (cdr L)) L
(append (my-quicksort (remove-if-not #'(lambda (x)
(funcall pred x (car L)))
(cdr L))
pred)
(list (car L))
(my-quicksort (remove-if-not #'(lambda (x)
(funcall (complement pred)
x (car L)))
(cdr L))
pred))))