Сортировать список в схеме

Обычно, когда мы говорим о сортировке, мы имеем в виду упорядочение элементов по какой-либо характеристике содержимого элемента, а не позиции элемента в списке. Я бы назвал вашу ситуацию перестановкой, но, возможно, некоторые люди могут оспорить и это использование. :-)

Вот как можно подойти к проблеме:

1. Разделите список посередине (вы можете сделать это, используя черепаху и зайца, если хотите пройти по списку только один раз); назовите эти списки head и tail, если хотите.
2. Переверните список tail и чередуйте его со списком head.

Другой подход:

1. Переверните исходные пары списков (назовем их rev).
2. Чередуйте исходный список с rev, отслеживая каждый раз пройденный элемент. Когда они встретятся посередине, остановитесь.

Вот демонстрация второго подхода (требуется загрузка SRFI 1) :

(define (zippy lst)
  (if (null? lst)
      '()
      (let recur ((lst lst)
                  (rev (pair-fold cons '() lst)))
        (cond ((eq? lst (car rev)) (list (car lst)))
              ((eq? (cdr lst) (car rev)) (list (car lst) (caar rev)))
              (else (cons* (car lst) (caar rev)
                           (recur (cdr lst) (cdr rev))))))))

На самом деле это не операция сортировки, а скорее перетасовка; вот еще один способ решить эту проблему. Во-первых, давайте определим процедуру interleave, которая чередует элементы из двух списков, возвращая один список:

(define (interleave l1 l2)
  (cond ((empty? l1) l2)
        ((empty? l2) l1)
        (else (cons (first l1)
                    (interleave l2 (rest l1))))))

Теперь берем исходный список и split-at посередине (эта процедура специфична для Racket); наконец, мы чередуем два получившихся списка, меняя хвост:

(define (zippy lst)
  (let-values (((head tail) (split-at lst (quotient (length lst) 2))))
    (interleave head (reverse tail))))

Вышеупомянутая реализация IMHO немного более интуитивно понятна, и если вы работаете с Racket, она не требует внешних библиотек. Он работает так, как ожидалось:

(zippy '(1 2 3 4 5 6))
=> '(1 6 2 5 3 4)