mergesort using the same trick as SICP 2.64 to avoid intermediate random access vector

mergesort.rkt

#lang racket

;; Implementation of a mergesort on lists, while avoiding intermediate
;; vector construction.  Uses the same trick as that in SICP Exercise
;; 2.64 to keep track of the elements we haven't yet processed.


(provide mergesort)

(define (mergesort elts)
  (define N (length elts))

  ;; mergesort-partially: list number -> (values list list)
  ;; Returns the sorted list of k elements, along with the rest of the
  ;; unprocessed elements in elts.
  (define (mergesort-partially elts k)
    (cond
     [(< k 2)
      ;; A list of less than 2 elements is sorted by definition.
      (split-at elts k)]
     [else
      (define m (quotient k 2))
      (define-values (left right-and-unprocessed-rest)
        (split-at elts m))
      (define-values (sorted-left _) 
        (mergesort-partially left m))
      (define-values (sorted-right unprocessed-rest) 
        (mergesort-partially right-and-unprocessed-rest (- k m)))
      (values (merge sorted-left sorted-right)
              unprocessed-rest)]))

  (define (merge l r)
    (cond
     [(empty? l)
      r]
     [(empty? r)
      l]
     [(<= (first l) (first r))
      (cons (first l)
            (merge (rest l) r))]
     [else
      (cons (first r)
            (merge l (rest r)))]))

  (define-values (sorted-elts _) 
    (mergesort-partially elts N))
  sorted-elts)


(module+ test
  (require rackunit)
  (check-equal? (mergesort '()) '())
  (check-equal? (mergesort '(1)) '(1))
  (check-equal? (mergesort '(1 2)) '(1 2))
  (check-equal? (mergesort '(2 1)) '(1 2))
  (check-equal? (mergesort '(1 2 3)) '(1 2 3))
  (check-equal? (mergesort '(1 3 2)) '(1 2 3))
  (check-equal? (mergesort '(3 1 2)) '(1 2 3))
  (check-equal? (mergesort '(3 2 1)) '(1 2 3))
  (check-equal? (mergesort '(2 1 3)) '(1 2 3))

  (check-equal? (mergesort '(1 2 3 4)) '(1 2 3 4))
  (check-equal? (mergesort '(1 2 4 3)) '(1 2 3 4))
  (check-equal? (mergesort '(1 4 2 3)) '(1 2 3 4))
  (check-equal? (mergesort '(1 4 3 2)) '(1 2 3 4))
  (check-equal? (mergesort '(4 1 2 3)) '(1 2 3 4))
  (check-equal? (mergesort '(4 1 3 2)) '(1 2 3 4))
  (check-equal? (mergesort '(4 3 1 2)) '(1 2 3 4))
  (check-equal? (mergesort '(4 3 2 1)) '(1 2 3 4))

  (check-equal? (mergesort '(3 1 4 1 5)) '(1 1 3 4 5))
  (check-equal? (mergesort '(5 4 3 2 1)) '(1 2 3 4 5)))