(define (enumerate! fortuita numerata)
  (loop ((for x (in-vector fortuita)))
    (vector-set! numerata x (+ (vector-ref numerata x) 1))))

(define (leq! numerata)
  (loop ((for x i (in-vector numerata 1)))
    (vector-set! numerata i (+ x (vector-ref numerata (- i 1))))))

(define (sort! numerata sortita x)
  (let ((count-index (- (vector-ref numerata x) 1)))
    (vector-set! sortita count-index x)
    (vector-set! numerata x count-index)))

(define (vector-max vector)
  ;; This will generate better code at the cost of assuming VECTOR to
  ;; be non-empty.  The uncommented form will yield #F in that case.
  ;; (collect-maximum (initial (vector-ref vector 0))
  ;;     (for x (in-vector vector 1))
  ;;   x)
  (collect-maximum (for x (in-vector vector))
    x))

(define (make-numerata fortuita)
  (make-vector (+ (vector-max fortuita) 1) 0))

(define (counting-sort fortuita)
  (let ((sortita (make-vector (vector-length fortuita)))
        (numerata (make-numerata fortuita)))
    (enumerate! fortuita numerata)
    (leq! numerata)
    (loop ((for x (in-vector-reverse fortuita)))
      (sort! numerata sortita x))
    sortita))