Time merge sort vs insertion sort

time_sorts.rkt

#lang racket
;; Generate a random list
;;  n:  list is length n
;;  mx: maximum value to generate
(define (randomlist n mx)
  (cond
    [(= n 0) empty]
    [else
     (cons (+ 1 (random mx))
           (randomlist (- n 1) mx))]))

;; Insertion Sort implementation
;; from https://gist.github.com/miyukino/5652107
(define (insert L M)
  (if (null? L) M
      (if (null? M) L
          (if (< (car L) (car M))
              (cons (car L) (insert (cdr L) M))
              (cons (car M) (insert (cdr M) L))))))

;; another insert function
;; need to modify the first para in insertionsort function to (car L)
(define (insert2 x L)
  (if (null? L) (list x)
      (let ((y (car L)) (M (cdr L)))
        (if (< x y)
            (cons x L)
            (cons y (insert2 x M))))))

;; Exp. (insertionsort '(4 2 10 3 -1 5)) ==> (-1 2 3 4 5 10)
(define (insertionsort L)
  (if (null? L) '()
      (insert (list (car L)) (insertionsort (cdr L)))))


;; Merge Sort implementation
;; From https://gist.github.com/miyukino/5652105
;; Exp. (merge '(1 3 5 7 8 9 10) '(2 4 6)) ==> (1 2 3 4 5 6 7 8 9 10)
(define (merge L M)
  (if (null? L) M
      (if (null? M) L
          (if (< (car L) (car M))
              (cons (car L) (merge (cdr L) M))
              (cons (car M) (merge (cdr M) L))))))

;; split helper functions
(define (odd L)
  (if (null? L) '()
      (if (null? (cdr L)) (list (car L))
          (cons (car L) (odd (cddr L))))))
(define (even L)
  (if (null? L) '()
      (if (null? (cdr L)) '()
          (cons (cadr L) (even (cddr L))))))

;; Exp. (split '(a b c d e f g h i)) ==> ((a c e g i)(b d f h))
(define (split L)
  (cons (odd L) (cons (even L) `())))


;; Exp. (mergesort '(8 1 3 9 6 5 7 2 4 10)) ==> (1 2 3 4 5 6 7 8 9 10)
(define (mergesort L)
  (if (null? L) L
      (if (null? (cdr L)) L
          (merge
           (mergesort (car (split L)))
           (mergesort (cadr (split L)))))))








;; Searches for the first instance of insertion sort that's faster than some reference time.
;;
;; A new list is generated each time where `current` elements at the
;; beginning of the list are sorted and then remaining elements
;; are random.
(define (find-fastest current list-size reference-value)

  (define st (current-inexact-milliseconds))
  (insertionsort (take (append (range 1 (- list-size current))
                               (randomlist list-size 1024000))
                       list-size))
  (define sort-duration (- (current-inexact-milliseconds) st))

  (if (< sort-duration reference-value)
      (fprintf (current-output-port)
               "~a sorted elements is slower than ~a"
               current
               reference-value)
      (find-fastest (- current 1)
                    list-size
                    reference-value)))


;; Time an insertion sort of 10,000 random items
(let* ([rl (randomlist 25000 1024000)]
       [start-time (current-inexact-milliseconds)]
       [sorted-rl (insertionsort rl)]
       [sort-time (- (current-inexact-milliseconds) start-time)])
  (fprintf (current-output-port)
           "insertion sort took ~a milliseconds\n"
           sort-time)
  )


;; Time a merge sort of 10,000 random items
(define merge-sort-time
(let* ([rl (randomlist 25000 1024000)]
       [start-time (current-inexact-milliseconds)]
       [sorted-rl (mergesort rl)]
       [sort-time (- (current-inexact-milliseconds) start-time)])
  (fprintf (current-output-port)
           "merge sort took ~a milliseconds\n"
           sort-time)
  sort-time
  ))

(find-fastest 3000 25000 merge-sort-time)