(defun bucketsort (vector &key (key #'identity)) (macrolet ((k (x) `(funcall key ,x)) (s (x) `(aref start ,x)) (e (x) `(aref end ,x)) (v (x) `(aref vector ,x))) (let* ((min (v 0)) (max min)) ;; compute min and max elements (loop for i from 1 below (length vector) do (setf min (min min (k (v i))) max (max max (k (v i))))) (let ((start (make-array (list (1+ (- max min))) :initial-element 0)) (end (make-array (list (1+ (- max min))) :initial-element 0))) ;; count the number of elements of each key (loop for elem across vector do (incf (e (- (k elem) min)))) ;; compute end positions (loop for i from 1 below (length end) do (incf (e i) (e (1- i)))) ;; compute start positions (loop for i from 1 below (length start) do (setf (s i) (e (1- i)))) ;; sort the elements (loop for i from 0 below (length start) do (loop while (< (s i) (e i)) do (let ((pos (- (k (v (s i))) min))) (rotatef (v (s i)) (v (s pos))) (incf (s pos)))))))) vector)