qsort

qsort-lazy.clj

(defn sort-parts
  "Lazy, tail-recursive, incremental quicksort.  Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
   (loop [[part & parts] work]
     (if-let [[pivot & xs] (seq part)]
       (let [smaller? #(< % pivot)]
         (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
       (when-let [[x & parts] parts]
         (cons x (sort-parts parts)))))))

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

qsort-macro.clj

(set! *unchecked-math* true)

(defmacro swap [a i j]              ;;definline
  `(let [a# ~a
         i# ~i
         j# ~j
         t# (aget a# i#)]
     (aset a# i# (aget a# j#))
     (aset a# j# t#)))

(defmacro apartition [a pivot i j]
  `(let [pivot# ~pivot]
     (loop [i# ~i
            j# ~j]
       (if (<= i# j#)
         (let [v# (aget ~a i#)]
           (if (< v# pivot#)
             (recur (inc i#) j#)
             (do 
               (when (< i# j#) 
                 (aset ~a i# (aget ~a j#))
                 (aset ~a j# v#))
               (recur i# (dec j#)))))
         i#))))

(defn qsort 
  ([^longs a]
    (qsort a 0 (alength a)))
  ([^longs a ^long lo ^long hi]    
    (let [lo (int lo)
          hi (int hi)]
      (when
        (< (inc lo) hi)
        (let [pivot (aget a lo)
              split (dec (apartition a pivot (inc lo) (dec hi)))]
          (when (> split lo) (swap a lo split))
          (qsort a lo split)
          (qsort a (inc split) hi)))
      a)))

qsort-no-macro.clj

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

(defn ^longs swap [^longs a ^long i ^long j]
  (let [t (aget a i)]
    (aset a i (aget a j))
    (aset a j t)))

(defn ^long apartition [^longs a ^long pivot ^long i ^long j]
  (loop [i i j j]
    (if (<= i j)
      (let [v (aget a i)]
        (if (< v pivot)
          (recur (inc i) j)
          (do 
            (when (< i j) 
              (aset a i (aget a j))
              (aset a j v))
            (recur i (dec j)))))
      i)))

(defn qsort 
  ([^longs a]
     (qsort a 0 (long (alength a))))
  ([^longs a ^long lo ^long hi]    
     (when
         (< (inc lo) hi)
       (let [pivot (aget a lo)
             split (dec (apartition a pivot (inc lo) (dec hi)))]
         (when (> split lo)
           (swap a lo split))
         (qsort a lo split)
         (qsort a (inc split) hi)))
     a))

(defn ^longs rand-long-array []
  (let [rnd (java.util.Random.)] 
    (long-array (repeatedly 100000 #(.nextLong rnd)))))

(comment
  (dotimes [_ 10]
    (let [^longs as (rand-long-array)]
      (time
       (dotimes [_ 1] 
         (qsort as)))))
  )