Lazy QuickSort implementation in Clojure, from Joy of Clojure chapter 6.

joy-of-clojure-lazy-qsort.clj

(ns joy.q)
;; nil

(defn nom [n] (take n (repeatedly #(rand-int n))))
;; #'joy.q/nom

(defn sort-parts [work]
     (lazy-seq
      (loop [[part & parts] work]            ;; Pull apart work - note: work will be a list of lists.
        (if-let [[pivot & xs] (seq part)]    ;; This blows up unless work was a list of lists.
          (let [smaller? #(< % pivot)]       ;; define pivot comparison function.
            (recur (list*                    
                    (filter smaller? xs)     ;; work all < pivot
                    pivot                    ;; work pivot itself
                    (remove smaller? xs)     ;; work all > pivot
                    parts)))                 ;; concat parts
          (when-let [[x & parts] parts]      ;; sort rest if more parts
            (cons x (sort-parts parts)))))))
;; #'joy.q/sort-parts

(defn qsort [xs]
   (sort-parts (list xs)))    ;; The (list) function ensures that we pass sort-parts a list of lists.
;; #'joy.q/qsort

(qsort [2 1 4 3])
;; (1 2 3 4)

(qsort [1 214 2 412 12172 418 0 -1 248])
;; (-1 0 1 2 214 248 412 418 12172)