A lazy, incremental, and tail-recursive implementation of quick-sort. Algorithm originally found in "The Joy of Clojure", but re-implemented and uploaded here for future reference.

litr-quick-sort.clj

(defn quick-sort-lists [lists]
  (lazy-seq
   (loop [[selected & other-lists] lists]
     (cond (seq selected) 
           (let [[pivot & selected-others] selected
                 smaller-than-pivot? #(< %1 pivot)]
             (recur (list* (filter smaller-than-pivot? selected-others)
                           pivot
                           (remove smaller-than-pivot? selected-others)
                           other-lists)))
           (seq other-lists)
           (let [[smallest & other-items] other-lists]
             (cons smallest
                   (quick-sort-lists other-items)))
           :else ()))))
  
(defn quick-sort [items]
  (quick-sort-list (list items)))