Quicksort

;;; Quicksort
(defun swap (a i j)
  "swap two elements in an indexable sequence"
  (let ((tmp (get a i)))
    (put! a i  (get a j))
    (put! a j tmp)))

(defun random-list (size maxr)
  "make list of length size of random number from 0 upto maxr"
  (map (lambda (x) (random maxr))
       (range 0 size)))

(defun partition (a lo hi)
  "partition part of an indexable sequence a"
  (let ((pivot (get a hi))
        (i lo)
        (j lo))
    (while (< j hi)
      (when (< (get a j) pivot)
        (swap a i j)
        (setv i (+ i 1)))
      (setv j (+ j 1)))
    (swap a i hi)
    i))  

(defun quick-sort (a &OPTIONAL (lo 0) (hi (- (length a) 1)))
  "quick sort an indexable sequence or part of it if lo and hi parameters are set"
  (when (< lo hi)
    (let ((p (partition a lo hi)))
      (quick-sort a lo      (- p 1))
      (quick-sort a (+ p 1) hi)))
  a)

(let ((samples (list (random-list 32 100) ; list of random integers
                     ;; array of random integers
                     (append (make-array :size 0) (random-list 32 100)) 
                     ;; StringBuffer
                     (.N "StringBuffer" '("Hello people! How do you do?")) 
                     ;; list of Characters
                     (append () "Hello people! How do you do?")
                     ;; semantic versions
                     (map #'version '("0.1.2" "0.1.2-pre1" "0.1.2-pre2" "0.1.3" "0.1.2-pre1+10" "1.2.3")))))   
  (foreach (sample samples)
    (println "Using quick sort on:  " (type-of sample))
    (println "input:  " sample)
    (quick-sort sample)
    (println "output: " sample)
    (println)))

Output:

Using quick sort on:  class java.util.ArrayList
input:  [94, 1, 45, 18, 90, 2, 6, 35, 94, 20, 94, 28, 3, 26, 46, 49, 69, 66, 20, 50, 40, 76, 2, 92, 51, 54, 44, 73, 99, 85, 77, 47]
output: [1, 2, 2, 3, 6, 18, 20, 20, 26, 28, 35, 40, 44, 45, 46, 47, 49, 50, 51, 54, 66, 69, 73, 76, 77, 85, 90, 92, 94, 94, 94, 99]

Using quick sort on:  class [Ljava.lang.Object;
input:  [22, 32, 66, 43, 3, 10, 96, 47, 17, 42, 45, 57, 6, 78, 10, 1, 40, 26, 14, 96, 91, 17, 7, 35, 75, 41, 98, 4, 95, 3, 59, 83]
output: [1, 3, 3, 4, 6, 7, 10, 10, 14, 17, 17, 22, 26, 32, 35, 40, 41, 42, 43, 45, 47, 57, 59, 66, 75, 78, 83, 91, 95, 96, 96, 98]

Using quick sort on:  class java.lang.StringBuffer
input:  Hello people! How do you do?
output:      !?HHddeeelllooooooppuwy

Using quick sort on:  class java.util.ArrayList
input:  [H, e, l, l, o,  , p, e, o, p, l, e, !,  , H, o, w,  , d, o,  , y, o, u,  , d, o, ?]
output: [ ,  ,  ,  ,  , !, ?, H, H, d, d, e, e, e, l, l, l, o, o, o, o, o, o, p, p, u, w, y]

Using quick sort on:  class java.util.ArrayList
input:  [0.1.2, 0.1.2-pre1, 0.1.2-pre2, 0.1.3, 0.1.2-pre1+10, 1.2.3]
output: [0.1.2-pre1+10, 0.1.2-pre1, 0.1.2-pre2, 0.1.2, 0.1.3, 1.2.3]