Scheme: сортировка слиянием.

Представляю твоему вниманию алгоритм сортировки слиянием на языке Scheme. Если мне не изменяет память этот алгоритм очень удобно применять при сортировке данных на магнитных лентах. Аналогично спискам в примере ниже, данные сначала делятся на две части и записываются на магнитные ленты, а потом с этих лент сливаются вместе и записываются на третью. Для тех кто не в курсе, Scheme это диалект Lisp, созданный для того, чтобы профессорам из MIT было легче мучить студентов.

";" служит для обозначения комментариев в коде.
#lang scheme Используется интерпретатором для определения языка.

#lang scheme
;Делим список
(define (split ls)
  ;letrec создает область значений, это нужно для рекурсивного вызова split-h
  ;Зачем? Ну хз, я бы define использовал.
  (letrec ([split-h (lambda (ls ls1 ls2)
                      (cond
                        ;Если первый список подошел концу
                        [(or (null? ls) (null? (cdr ls)))
                         ;Делаем пару из второго списка и первого. 
                         ;Переворачиваем, так как при добавлении первым идет последний добавленный.
                         (cons (reverse ls2) ls1)]
                         ;По-начальному списку спускаемся на 2 элемента вниз,
                         ;по-первому на 1. Когда дойдем до конца во втором списке будет 
                         ;первая половина начального списка.
                        [else (split-h (cddr ls)
                                (cdr ls1) (cons (car ls1) ls2))]))])
    (split-h ls ls '())))
;Сливаем списки, тут на мой взгяд все очевидно.
(define (merge pred ls1 ls2)
  (cond
    [(null? ls1) ls2]
    [(null? ls2) ls1]
    [(pred (car ls1) (car ls2))
     (cons (car ls1) (merge pred (cdr ls1) ls2))]
    [else (cons (car ls2) (merge pred ls1 (cdr ls2)))]))

(define (merge-sort pred ls)
  (cond
    [(null? ls) ls]
    [(null? (cdr ls)) ls]
    [else (let ([splits (split ls)])
            ;Вот тут довольно неприятный рекурсивный вызов.
            ;Он не позволит использовать в точности этот алгоритм для 
            ;магнитных лент.
            (merge pred
              (merge-sort pred (car splits))
              (merge-sort pred (cdr splits))))]))

Оригинальная статься по данному алгоритму содержит лицензию, которую я надеюсь не нарушаю. В работе алгоритма я убедился в замечательной среде PLT-Scheme .

Некоторую проблему для меня создали квадратные скобки. Немного поискав, я узнал, что они аналогичны круглым скобкам и служат в основном для подчеркивания того, что заключенный в них код не является вызовом функций.

Если у тебя есть вопросы по работе алгоритма, или злобный преподаватель хочет модификацию, приведенного алгоритма, смело спрашивай в комментах.