sort.lisp

(defun insert (cmp target list)
  "Insert the target into a sorted list."
  (if (null list)
      (cons target '())
      (if (funcall cmp target (first list))
	  (cons target list)
	  (cons (first list) (insert cmp target (rest list))))))

(defun insertionSort (cmp list)
  "Insertion Sort, a recursive version."
  (if (null list)
      '()
      (insert cmp (first list) (insertionSort cmp (rest list)))))

(defun quickSort (cmp list)
  "Quicksort...usage: (quickSort #'< list)"
  (cond
    ((null list) '())
    (T (let* ((x (first list))
              (less (remove-if-not #'(lambda (y) (funcall cmp y x)) list))
              (greater (remove-if-not #'(lambda (y) (funcall cmp x y)) list)))
         (append (quickSort cmp less) (cons x (quickSort cmp greater)))))))