(defn- swap [source idx0 idx1]
  (def tmp (aget source idx0))
  (aset source idx0 (aget source idx1))
  (aset source idx1 tmp))

; find median among start/mid/end
(defn- get-pivot [source start len]
  (let [end (+ start (dec len)) mid (+ start (int (/ len 2)))]
    (if
      (or
        (and
          (> (aget source start) (aget source mid))
          (< (aget source start) (aget source end)))
        (and
          (> (aget source start) (aget source end))
          (< (aget source start) (aget source mid))))
      start
      ; else if
      (if
        (or
          (and
            (> (aget source mid) (aget source start))
            (< (aget source mid) (aget source end)))
          (and
            (> (aget source mid) (aget source end))
            (< (aget source mid) (aget source start))))
        mid
        ; else
        end))))

(defn- get-left-idx [source start pivot]
  (loop [idx start]
    (if (and (< (aget source idx) (aget source pivot)) (not= pivot idx)) (recur (inc idx)) idx)))

(defn- get-right-idx [source start pivot]
  (loop [idx start]
    (if (and (> (aget source idx) (aget source pivot)) (not= pivot idx)) (recur (dec idx)) idx)))

(defn- comp-and-swap [source start len]
  (loop [leftIdx start rightIdx (+ start (dec len)) pivot (get-pivot source start len)]
    (let [compLeftIdx (get-left-idx source leftIdx, pivot) compRightIdx (get-right-idx source rightIdx pivot)]
      (if (and (= compLeftIdx pivot) (not= compRightIdx pivot))
        (do
          (swap source pivot (inc pivot))
          (if (> (- compRightIdx pivot) 1) (swap source pivot compRightIdx))
          (recur (inc pivot) compRightIdx (inc pivot)))
        ; else if
        (if (and (= compRightIdx pivot) (not= compLeftIdx pivot))
          (do
            (swap source pivot (dec pivot))
            (if (> (- pivot compLeftIdx) 1) (swap source pivot compLeftIdx))
            (recur compLeftIdx (dec pivot) (dec pivot)))
          ; else if
          (if (not= compLeftIdx compRightIdx)
            (do
              (swap source compLeftIdx compRightIdx)
              (recur (inc compLeftIdx) (dec compRightIdx) pivot))
            ; else
            compLeftIdx))))))

(defn- do-sort [source start len]
  (let [mid (+ (comp-and-swap source start len) 1)]
    (if (> len 2)
      (do
        (do-sort source start (- mid start))
        (do-sort source mid (- (+ start len) mid))))))

(defn quicksort [source]
  (do-sort source 0 (alength source)))