(defn qsort [xs]
  (loop [[part & parts :as work] (list xs), out []]
    (if-not work
      out
      (cond
        (coll? part) (let [[pivot & xs] part, smaller #(< % pivot)]
                      (recur (conj parts
                                    (seq (remove smaller xs))
                                    pivot
                                    (seq (filter smaller xs)))
                              out))
        (nil? part) (recur parts out)
        part (recur parts (conj out part))))))

(defn cons-when [v coll]
  (if (empty? v) coll (cons v coll)))

(defn sort-parts [work]
  (lazy-seq
    (loop [[part & parts :as work] work]
      (when work
        (if (coll? part)
          (let [[pivot & xs] part, smaller #(< % pivot)]
            (recur (cons-when
                     (filter smaller xs)
                     (cons pivot (cons-when (remove smaller xs) parts)))))
          (cons part (sort-parts parts)))))))

(defn qsort [xs]
  (sort-parts (list xs)))