Counts the number of inversions in a vector of numbers, using merge sort

count-inversions.rkt

#lang racket

(provide count-inversions count-inversions!)

;; A solution to Exercise 2.2d of CLRS.  Counts the number of inversions
;; in a vector of numbers, using a modified merge sort.

;; count-inversions: vector -> number
(define (count-inversions v)
  (count-inversions! (vector-copy v)))


;; count-inversions!: vector -> number
(define (count-inversions! v)
  (define N (vector-length v))
  (cond
   [(< N 2)
    0]
   [else
    (define midpoint (quotient N 2))
    (define left 
      (build-vector midpoint
                    (lambda (i)
                      (vector-ref v i))))
    (define right
      (build-vector (- N midpoint)
                    (lambda (i) 
                      (vector-ref v (+ i midpoint)))))
    (define i1 (count-inversions! left))
    (define i2 (count-inversions! right))
    (+ i1 i2 (merge! left right v))]))

(define (merge! left right target)
  (define M (vector-length left))
  (let loop ([i 0]
             [j 0]
             [k 0]
             [inversions 0])
    (cond
     [(= k (vector-length target))
      inversions]
     [(and (not (= i (vector-length left)))
           (or (= j (vector-length right))
               (<= (vector-ref left i) (vector-ref right j))))
      (vector-set! target k (vector-ref left i))
      (loop (add1 i) j (add1 k) inversions)]
     [else
      (vector-set! target k (vector-ref right j))
      (loop i (add1 j) (add1 k) (+ inversions (- M i)))])))


(module+ test
  (require rackunit)
  (check-equal? (count-inversions #(2 3 8 6 1)) 5)
  (check-equal? (count-inversions #(1 2 3 4 5)) 0)
  (check-equal? (count-inversions #(2 1 3 4 5)) 1)
  (check-equal? (count-inversions #(3 1 4 2 5)) 3)

  (check-equal? (count-inversions #(2 3 8 6)) 1)
  (check-equal? (count-inversions #(1 2 3 4)) 0)
  (check-equal? (count-inversions #(2 1 3 4)) 1)
  (check-equal? (count-inversions #(3 1 4 2)) 3)

  (check-equal? (count-inversions #(1 2 3)) 0)
  (check-equal? (count-inversions #(1 3 2)) 1)
  (check-equal? (count-inversions #(2 1 3)) 1)
  (check-equal? (count-inversions #(3 2 1)) 3)

  (check-equal? (count-inversions #(1 2)) 0)
  (check-equal? (count-inversions #(2 1)) 1)

  (check-equal? (count-inversions #(1)) 0)

  (check-equal? (count-inversions #()) 0))