Racket：使用递归制作归并排序函数

Question

我有一个 Racket 作业问题，要求我使用递归创建一个

mergesort

函数。它应该获取一个列表，将其分成更小的列表，然后将它们从小到大排序。该函数还应该返回排序列表，而无需在此作业中使用任何排序命令。

这是我到目前为止的代码：

(define (mergesort lst)
  (cond
    [(empty? lst) '()]
    [(= (length lst) 1) lst]
    [(let* ([index 0][end_index (- (length lst) 1)])
       (if (< (list-ref lst index) (list-ref lst (add1 index)))
           (cons...)
           (cons...) 
           ))]
    )
  )

(mergesort '(3 1 2 7 9)) ;should return (1 2 3 7 9)

我正在努力弄清楚当满足 if 语句时如何将元素移动到正确的位置（从最小到最大）。我走在正确的道路上吗？

Answer 1

要将列表拆分为两个子列表，您可以使用函数

take

和

drop

。例如：

> (define L '(5 9 1 3 7 0 8 4 6 2))

> (take L 5) ; get the first 5 elements in L
'(5 9 1 3 7)

> (drop L 5) ; skip the first 5 elements in L and get the rest
'(0 8 4 6 2)
> 

给定两个 sorted 列表，以下函数返回一个 sorted 列表，其中包含两个列表中的所有元素：

(define (merge A B)
    (cond [(empty? A) B]
          [(empty? B) A]
          [(<= (first A) (first B)) (cons (first A) (merge (rest A) B))]
          [else                     (cons (first B) (merge A (rest B)))]))

例如：

> (merge '(0 1 3 6 7) '(2 4 5 8 9))
'(0 1 2 3 4 5 6 7 8 9)

因此，合并排序算法可以编码如下：

(define (merge-sort L)
  (let ((k (quotient (length L) 2)))
    (cond [(zero? k) L]
          [else (merge (merge-sort (take L k))
                       (merge-sort (drop L k)))])))

示例：

> (merge-sort '(5 9 1 3 7 0 8 4 6 2))
'(0 1 2 3 4 5 6 7 8 9)
>