scheme language bottom up mergesort code

;; Merge two sorted lists using the given comparator
(define (merge comparator list1 list2)
  (define (merge01 l1 l2 acc)
    (cond
      ((null? l2) (append (reverse acc) l1))
      ((null? l1) (append (reverse acc) l2))
      ((comparator (car l2) (car l1))
       (merge01 l1 (cdr l2) (cons (car l2) acc)))
      (else
       (merge01 (cdr l1) l2 (cons (car l1) acc)))))
  (merge01 list1 list2 '()))

;; Prepare each element as a singleton list
(define (sort01 jumble)
  (map list jumble))

;; Perform one pass of merging adjacent pairs
(define (sort02 comparator lists)
  (cond
    ((null? lists) '())
    ((null? (cdr lists)) lists)
    (else
     (cons (merge comparator (car lists) (cadr lists))
           (sort02 comparator (cddr lists))))))

;; Repeatedly merge until one list remains
(define (sort03 comparator lists)
  (cond
    ((null? lists) '())
    ((null? (cdr lists)) (car lists))
    (else
     (sort03 comparator (sort02 comparator lists)))))

;; Top‐level sort: prepare, merge‐pass, then finalize
(define (sort comparator jumble)
  (sort03 comparator (sort02 comparator (sort01 jumble))))

;; Entry point: sort the sample list in descending order then display
(define (main)
  (display (sort > '(4 3 5 6 8 7 1 2 9)))
  (newline))