Мне известно о stdlib Ракета , но я хочу сам реализовать функцию сортировки в качестве упражнения.Я решил использовать алгоритм сортировки слиянием, так как он естественно определен в рекурсивных терминах.Довольно скоро я придумала рабочий код, но он работает слишком медленно .Мне кажется, что время выполнения экспоненциально от размера списка, хотя теоретически оно должно быть O(n·log n).
Вот мой код:
#lang racket</p>
<p>(define (pair x y) (list x y))</p>
<p>(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)))))]))</p>
<p>(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))))))</p>
<p>(define (sort input)
(cond
[(empty? input) null]
[(empty? (rest input)) input]
[else
(let [(halves (split input))]
(merge (sort (first halves)) (sort (second halves))))]))</p>
<p>(define (sorted? input)
(cond
[(empty? input) #t]
[(empty? (rest input)) #t]
[else
(and (<= (first input) (second input))
(sorted? (rest input)))]))
Кажется, я использую некоторые«атомная» операция, которая не выполняется постоянно, как мне кажется, однако я не могу понять, какая именно.Сортировка 30 случайных элементов происходит мгновенно, 40 элементов обрабатываются за пару секунд, 50 элементов занимают полминуты.Интересно, а где загвоздка?