Почему моя реализация сортировки слиянием в Scheme работает так медленно?

Я знаю о stdlib Racket , но я хочу реализовать функцию сортировки самостоятельно в качестве упражнения. Я решил использовать алгоритм сортировки слиянием, поскольку он естественно определяется в рекурсивных терминах. Довольно скоро у меня появился рабочий код, но он работает слишком медленно . Мне кажется, что время выполнения экспоненциально зависит от размера списка, хотя теоретически оно должно быть O (n · log n) .

Вот мой код:

#lang racket

(define (pair x y) (list x y))

(define (split input)
  (cond
    [(empty? input) (pair null null)]
    [(empty? (rest input)) (pair input null)]
    [else
     (let [(tail (cddr input))]
       (pair (cons (first input) (first (split tail)))
             (cons (second input) (second (split tail)))))]))

(define (merge input1 input2)
  (if (ormap empty? (list input1 input2))
      (append input1 input2)
      (if (< (first input1) (first input2))
          (cons (first input1) (merge (rest input1) input2))
          (cons (first input2) (merge input1 (rest input2))))))

(define (sort input)
  (cond
    [(empty? input) null]
    [(empty? (rest input)) input]
    [else
     (let [(halves (split input))]
       (merge (sort (first halves)) (sort (second halves))))]))

(define (sorted? input)
  (cond
    [(empty? input) #t]
    [(empty? (rest input)) #t]
    [else 
     (and (<= (first input) (second input))
          (sorted? (rest input)))]))

Похоже, что я использую некую «атомарную» операцию, которая не выполняется в постоянное время, как я мог подумать, однако я не могу понять, какая именно. Сортировка 30 случайных элементов происходит мгновенно, 40 элементов обрабатываются за пару секунд, 50 элементов занимают полминуты. Поэтому мне интересно, где же загвоздка? ​​