(defn sort-parts [work]
(lazy-seq
;; 'work' is a list whose elements can be either a sequence or a
;; singlemitem. E.g:
;; When sorting [3 7 1 4 2 5], the first loop will create a 'work'
;; as the following:
;; ((1 2) 3 (7 4 5))
;; Where first list (1 2) is elements before pivot, the second
;; element 3 is the pivot and the third (7 4 5) are elements larger
;; than pivot
(loop [[part & parts] work]
;; part in this case is a list containing elements smaller than
;; pivot
(if-let [[pivot & xs] (seq part)]
;; 'part' is not empty, choose first element as pivot,
;; recursively sort until part is empty. That is, until the
;; pivot is the smallest element.
(let [smaller? #(< % pivot)]
(recur (list*
(filter smaller? xs)
pivot
(remove smaller? xs)
parts)))
;; If part is empty, the the pivot (x) is the smallest element, so
;; return x as the first element. The rest are lazily evaluated.
(when-let [[x & parts] parts]
(cons x (sort-parts parts)))))))
(defn qsort [l]
(sort-parts (list l)))
