为什么我在Scheme中的合并排序实现如此之慢？

Question

我知道Racket的stdlib,但我想自己实现一个排序功能作为练习.我决定使用合并排序算法,因为它在递归术语中自然定义.很快我就提出了工作代码,但它运行得太慢了.在我看来,运行时间是列表大小的指数,虽然理论上它应该是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个项目需要半分钟.所以我想知道,障碍在哪里？

Answer 1

在split,您调用(split tail)两次而不是使用let它运行一次并将结果存储到变量中.这可能是split指数时间.