;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; bottom-up merge sort
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define merge-sort
  (lambda (num-list)
    (cond ((null? num-list) '())
          ((null? (cdr num-list)) num-list)
          (else (car (repeat-rounds (map list num-list)))))))

(define repeat-rounds
  (lambda (list-of-num-lists)
    (cond ((null? list-of-num-lists) '())
          ((null? (cdr list-of-num-lists)) list-of-num-lists)
          (else (repeat-rounds (one-round list-of-num-lists))))))

(define one-round
  (lambda (list-of-num-lists)
    (cond ((null? list-of-num-lists) '())
          ((null? (cdr list-of-num-lists)) list-of-num-lists)
          (else (cons (merge (car list-of-num-lists) (cadr list-of-num-lists))
                      (one-round (cddr list-of-num-lists)))))))

;; this version does not eliminate duplicates
(define merge
  (lambda (num-list1 num-list2)
    (cond ((null? num-list1) num-list2)
          ((null? num-list2) num-list1)
          ((< (car num-list1) (car num-list2))
           (cons (car num-list1) (merge (cdr num-list1) num-list2)))
          (else
           (cons (car num-list2) (merge num-list1 (cdr num-list2)))))))