shell_sort.lisp

(defun shellsort (gap-sequence-fn sequence)
  (let ((len (length sequence)))
    (unless (< len 2)
      (mapc (lambda (gap)
              (labels ((insert (x index)
                         (if (minusp index)
                             (setf (elt sequence (+ index gap)) x)
                             (let ((y (elt sequence index)))
                               (if (< x y)
                                   (progn
                                     (setf (elt sequence (+ index gap)) y)
                                     (insert x (- index gap)))
                                   (setf (elt sequence (+ index gap)) x)))))
                       (repeat-insertion (index)
                         (if (>= index len)
                             (values)
                             (progn
                               (insert (elt sequence index) (- index gap))
                               (repeat-insertion (+ index gap)))))
                       (h-sorting (h)
                         (if (zerop h)
                             (values)
                             (progn
                               (repeat-insertion (1- (+ h gap)))
                               (h-sorting (1- h))))))
                (h-sorting gap)))
            (funcall gap-sequence-fn len)))
    sequence))