Quicksort implementation courtesy of Introduction to Algorithms (3rd Ed.)

qsort.clj

(ns mefesto.qsort)

(set! *warn-on-reflection* true)

(defn- aswap! [^doubles vals ^ints idxs ^long x ^long y]
  (let [val (aget vals x)
        idx (aget idxs x)]
    (aset vals x (aget vals y))
    (aset vals y val)
    (aset idxs x (aget idxs y))
    (aset idxs y idx)))

(defn- partition! [^doubles vals ^ints idxs ^long p ^long r]
  (let [res (loop [i (dec p) j p]
              (if (>= j r)
                i
                (if-not (<= (aget vals j) (aget vals r))
                  (recur i (inc j))
                  (do (aswap! vals idxs (inc i) j)
                      (recur (inc i) (inc j))))))]
    (aswap! vals idxs (inc res) r)
    (inc res)))

(defn qsort!
  ([^doubles vals ^ints idxs]
     (qsort! vals idxs 0 (dec (count vals))))
  ([^doubles vals ^ints idxs ^long p ^long r]
     (when (< p r)
       (let [q (partition! vals idxs p r)]
         (qsort! vals idxs p (dec q))
         (qsort! vals idxs (inc q) r)))))

repl

;; Test
(let [vals (into-array Double/TYPE [0.2 0.3 0.1 0.5 0.9 0.7 0.6 0.4 0.8])
      idxs (into-array Integer/TYPE (range (count vals)))]
  (time (qsort! vals idxs))
  (println (seq vals))
  (println (seq idxs)))

;; Results
"Elapsed time: 0.628486 msecs"
(0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9)
(2 0 1 7 3 6 5 8 4)

"Elapsed time: 0.105836 msecs"
(0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9)
(2 0 1 7 3 6 5 8 4)