non-recursive quicksort

gistfile1.lisp

;;; non-recursive quicksort
;;; http://bertrandmeyer.com/2014/12/07/lampsort/

(defun partition (array low high)
  (let ((pivot-value (aref array high))
        (insert-at   low))
    (loop for i from low upto high do
          (when (< (aref array i) pivot-value)
            (rotatef (aref array i) (aref array insert-at))
            (incf insert-at)))
    (rotatef (aref array high) (aref array insert-at))
    insert-at))

(defun quicksort-lamport (array predicate &aux (intervals (list (cons 0 (1- (length array))))))
  (loop while intervals do
        (destructuring-bind (low . high)
            (pop intervals)
          (when (funcall predicate low high)
            (let ((pivot (partition array low high)))
              (push (cons low (1- pivot))  intervals)
              (push (cons (1+ pivot) high) intervals)))))
  array)