;; Time Complexity from O(n log(n)) to O(n^2)
;; Space Complexity O(log(n))

;; no indices to juggle: filter splits the tail by the pivot
(defn quick-sort [coll]
  (if (< (count coll) 2)
    (vec coll)
    (let [pivot (first coll)
          others (rest coll)]
      (into (conj (quick-sort (filter #(< % pivot) others)) pivot)
            (quick-sort (filter #(>= % pivot) others))))))

(def items [4 1 5 3 2])
(def sort-items (quick-sort items))
;; sort-items is [1 2 3 4 5]

(prn items)
(prn sort-items)
(println "same as built-in sort:" (= sort-items (sort items)))