heap.rkt

#lang racket

(require data/heap)

(define input (for/list ([ _ (in-range 115000) ])
                (random-string 15)))

(define (with-heap)
  (define obj (make-heap string<?))

  (for ([ s (in-list input) ])
    (heap-add! obj s))

  (heap-min obj))

(define (with-sort)
  (let loop ([ input input ][ result '() ])
    (if (null? input)
        (car result)
        (loop (cdr input)
              (sort (cons (car input) result)
                    string<?)))))

(define (with-insertion)
  (define (insert s lst)
    (cond [ (null? lst)
            (cons s lst) ]
          [ (string<? s (car lst))
            (cons s lst) ]
          [ else
            (cons (car lst) (insert s (cdr lst))) ]))

  (let loop ([ strs input ]
             [ result '() ])
    (if (null? strs)
        (car result)
        (loop (cdr strs) (insert (car strs) result)))))
        
(time (with-heap))