mergesort.rkt

#lang racket

;; Merge sort (imperative version)
;;
;; MergeSort(arr[], l,  r)
;; If r > l
;;   1. Find the middle point to divide the array into two halves:  
;;             middle m = (l+r)/2
;;   2. Call mergeSort for first half:   
;;           Call mergeSort(arr, l, m)
;;   3. Call mergeSort for second half:
;;           Call mergeSort(arr, m+1, r)
;;   4. Merge the two halves sorted in step 2 and 3:
;;           Call merge(arr, l, m, r)

;; return multiple values via cons
(define (list-split l)
  (define n (length l))
  (define half-length (truncate (/ n 2)))
  (define (loop l i acc)
    (if (= i 0)
        (cons (reverse acc) l)
        (loop (cdr l) (- i 1) (cons (car l) acc))))
  (loop l half-length '()))

(define (merge-sort l)
  ;; (merge '(0 5 6) '(1 2 7))
  ;; '(0 1 2 5 6 7)
  (define (merge l0 l1 acc)
    ;;(displayln (format "merge ~a ~a ~a" l0 l1 acc))
    (define (loop l0 l1 acc)
      (match (cons l0 l1)
        ;; They're both empty
        [(cons '() '())
         ;; Reverse accumulator and return
         (reverse acc)]
        [(cons '() l)
         (append (reverse acc) l)]
        [(cons l '())
         (append (reverse acc) l)]
        [(cons `(,hd0 . ,tl0) `(,hd1 . ,tl1))
         (if (> hd0 hd1)
             (loop l0 tl1 (cons hd1 acc))
             (loop tl0 l1 (cons hd0 acc)))]))
    (loop l0 l1 '()))
  (if (= (length l) 1)
      ;; Base case: if the list is of length 1, just return l
      l
      ;; Inductive case: if the list is of length > 1:
      ;; - split list into two
      ;; - call merge-sort on both sublists
      ;; - merge each sublist back together
      (match (list-split l)
        [(cons first second)
         ;; (displayln (format "first: ~a merge-sort of first: ~a" first (merge-sort first)))
         ;; (displayln (format "second: ~a merge-sort of second: ~a" second (merge-sort second)))
         (merge (merge-sort first) (merge-sort second) '())])))

(define (generate-random-list i)
  (if (= i 0) '()
      (cons (random 0 200000) (generate-random-list (- i 1)))))

(for ([i (range 0 5000)])
  (let ([input-list (generate-random-list 50)])
    (if (equal? (merge-sort input-list) (sort input-list <))
        (displayln "passed")
        (begin
          (displayln "failed:")
          (pretty-print input-list)
          (displayln "correct answer:")
          (pretty-print (sort input-list <))
          (displayln "our answer:")
          (pretty-print (merge-sort input-list))))))