(defun num-cmp (a b)
  (< a b))
 
;; Функция сравнения для символов
(defun sym-cmp (a b)
  (string< (string a) (string b)))
 
;; Генерация тестовых данных
(defun generate-random-list (n)
  (loop repeat n collect (random 1000)))
 
;; =====================================================================
;; Сортировка Шелла
;; Последовательность Седжвика
(defun sedgewick-sequence (n)
  (labels ((sedgewick-iter (k seq)
             (let ((next (+ (* 4 (expt 2 k)) (* 3 (expt 2 (1- k))) 1)))
               (if (> next n)
                   (reverse seq)
                   (sedgewick-iter (1+ k) (cons next seq))))))
    (if (<= n 1)
        '(1)
        (sedgewick-iter 1 '(1)))))
 
;; Сортировка вставками с шагом
(defun insertion-sort-step (lst step cmp)
  (let ((n (length lst)))
    (loop for i from step below n
          do (let ((temp (nth i lst))
                   (j i))
               (loop while (and (>= j step) (funcall cmp temp (nth (- j step) lst)))
                     do (setf (nth j lst) (nth (- j step) lst))
                        (decf j step))
               (setf (nth j lst) temp))))
  lst)
 
;; Основная функция сортировки Шелла
(defun shell-sort (lst cmp)
  (let ((n (length lst)))
    (if (<= n 1)
        lst
        (let ((steps (sedgewick-sequence n)))
          (shell-sort-with-steps lst steps cmp)))))
 
;; Сортировка с последовательностью шагов
(defun shell-sort-with-steps (lst steps cmp)
  (if (null steps)
      lst
      (shell-sort-with-steps
       (insertion-sort-step lst (car steps) cmp)
       (cdr steps)
       cmp)))
 
;; Итеративная сортировка бинарными вставками (in-place)
(defun binary-insertion-sort (list cmp)
  (let ((n (length list)))
    (loop for i from 1 below n
          do (let ((key (nth i list))
                   (left 0)
                   (right i))
 
               ;; Бинарный поиск позиции для вставки
               (loop while (< left right)
                     do (let ((mid (floor (+ left right) 2)))
                          (if (funcall cmp key (nth mid list))
                              (setf right mid)
                              (setf left (1+ mid)))))
 
               ;; Сдвиг элементов вправо, чтобы освободить место
               (loop for j from i downto (1+ left)
                     do (setf (nth j list) (nth (1- j) list)))
 
               ;; Вставка элемента
               (setf (nth left list) key))))
  list)
 
;; Функция для тестирования (пример использования num-cmp)
(defun test-binary-insertion-sort ()
  (let ((test-list (list 5 2 8 1 9 4)))
    (format t "Original list: ~a~%" test-list)
    (let ((sorted-list (binary-insertion-sort (copy-list test-list) #'num-cmp))) ; Важно: copy-list
      (format t "Sorted list:   ~a~%" sorted-list))))
 
;; =====================================================================
;; Тестирование
(let* ((test-size 100) ; Размер списка можно менять
       (test-data (generate-random-list test-size))) ; Removed unnecessary copy
  (format t "Исходные данные (первые 10 элементов): ~a...~%" (subseq test-data 0 (min 10 (length test-data))))
 
  (format t "~%Сортировка Шелла:~%")
  (time (shell-sort (copy-list test-data) #'num-cmp)) ; Создаем копию перед сортировкой
 
  (format t "~%Сортировка бинарными вставками:~%")
  (time (binary-insertion-sort (copy-list test-data) #'num-cmp))) ; Создаем копию перед сортировкой
 
;; Запуск теста
(test-binary-insertion-sort)

KGRlZnVuIG51bS1jbXAgKGEgYikKICAoPCBhIGIpKQoKOzsg0KTRg9C90LrRhtC40Y8g0YHRgNCw0LLQvdC10L3QuNGPINC00LvRjyDRgdC40LzQstC+0LvQvtCyCihkZWZ1biBzeW0tY21wIChhIGIpCiAgKHN0cmluZzwgKHN0cmluZyBhKSAoc3RyaW5nIGIpKSkKCjs7INCT0LXQvdC10YDQsNGG0LjRjyDRgtC10YHRgtC+0LLRi9GFINC00LDQvdC90YvRhQooZGVmdW4gZ2VuZXJhdGUtcmFuZG9tLWxpc3QgKG4pCiAgKGxvb3AgcmVwZWF0IG4gY29sbGVjdCAocmFuZG9tIDEwMDApKSkKCjs7ID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQo7OyDQodC+0YDRgtC40YDQvtCy0LrQsCDQqNC10LvQu9CwCjs7INCf0L7RgdC70LXQtNC+0LLQsNGC0LXQu9GM0L3QvtGB0YLRjCDQodC10LTQttCy0LjQutCwCihkZWZ1biBzZWRnZXdpY2stc2VxdWVuY2UgKG4pCiAgKGxhYmVscyAoKHNlZGdld2ljay1pdGVyIChrIHNlcSkKICAgICAgICAgICAgIChsZXQgKChuZXh0ICgrICgqIDQgKGV4cHQgMiBrKSkgKCogMyAoZXhwdCAyICgxLSBrKSkpIDEpKSkKICAgICAgICAgICAgICAgKGlmICg+IG5leHQgbikKICAgICAgICAgICAgICAgICAgIChyZXZlcnNlIHNlcSkKICAgICAgICAgICAgICAgICAgIChzZWRnZXdpY2staXRlciAoMSsgaykgKGNvbnMgbmV4dCBzZXEpKSkpKSkKICAgIChpZiAoPD0gbiAxKQogICAgICAgICcoMSkKICAgICAgICAoc2VkZ2V3aWNrLWl0ZXIgMSAnKDEpKSkpKQoKOzsg0KHQvtGA0YLQuNGA0L7QstC60LAg0LLRgdGC0LDQstC60LDQvNC4INGBINGI0LDQs9C+0LwKKGRlZnVuIGluc2VydGlvbi1zb3J0LXN0ZXAgKGxzdCBzdGVwIGNtcCkKICAobGV0ICgobiAobGVuZ3RoIGxzdCkpKQogICAgKGxvb3AgZm9yIGkgZnJvbSBzdGVwIGJlbG93IG4KICAgICAgICAgIGRvIChsZXQgKCh0ZW1wIChudGggaSBsc3QpKQogICAgICAgICAgICAgICAgICAgKGogaSkpCiAgICAgICAgICAgICAgIChsb29wIHdoaWxlIChhbmQgKD49IGogc3RlcCkgKGZ1bmNhbGwgY21wIHRlbXAgKG50aCAoLSBqIHN0ZXApIGxzdCkpKQogICAgICAgICAgICAgICAgICAgICBkbyAoc2V0ZiAobnRoIGogbHN0KSAobnRoICgtIGogc3RlcCkgbHN0KSkKICAgICAgICAgICAgICAgICAgICAgICAgKGRlY2YgaiBzdGVwKSkKICAgICAgICAgICAgICAgKHNldGYgKG50aCBqIGxzdCkgdGVtcCkpKSkKICBsc3QpCgo7OyDQntGB0L3QvtCy0L3QsNGPINGE0YPQvdC60YbQuNGPINGB0L7RgNGC0LjRgNC+0LLQutC4INCo0LXQu9C70LAKKGRlZnVuIHNoZWxsLXNvcnQgKGxzdCBjbXApCiAgKGxldCAoKG4gKGxlbmd0aCBsc3QpKSkKICAgIChpZiAoPD0gbiAxKQogICAgICAgIGxzdAogICAgICAgIChsZXQgKChzdGVwcyAoc2VkZ2V3aWNrLXNlcXVlbmNlIG4pKSkKICAgICAgICAgIChzaGVsbC1zb3J0LXdpdGgtc3RlcHMgbHN0IHN0ZXBzIGNtcCkpKSkpCgo7OyDQodC+0YDRgtC40YDQvtCy0LrQsCDRgSDQv9C+0YHQu9C10LTQvtCy0LDRgtC10LvRjNC90L7RgdGC0YzRjiDRiNCw0LPQvtCyCihkZWZ1biBzaGVsbC1zb3J0LXdpdGgtc3RlcHMgKGxzdCBzdGVwcyBjbXApCiAgKGlmIChudWxsIHN0ZXBzKQogICAgICBsc3QKICAgICAgKHNoZWxsLXNvcnQtd2l0aC1zdGVwcwogICAgICAgKGluc2VydGlvbi1zb3J0LXN0ZXAgbHN0IChjYXIgc3RlcHMpIGNtcCkKICAgICAgIChjZHIgc3RlcHMpCiAgICAgICBjbXApKSkKCjs7INCY0YLQtdGA0LDRgtC40LLQvdCw0Y8g0YHQvtGA0YLQuNGA0L7QstC60LAg0LHQuNC90LDRgNC90YvQvNC4INCy0YHRgtCw0LLQutCw0LzQuCAoaW4tcGxhY2UpCihkZWZ1biBiaW5hcnktaW5zZXJ0aW9uLXNvcnQgKGxpc3QgY21wKQogIChsZXQgKChuIChsZW5ndGggbGlzdCkpKQogICAgKGxvb3AgZm9yIGkgZnJvbSAxIGJlbG93IG4KICAgICAgICAgIGRvIChsZXQgKChrZXkgKG50aCBpIGxpc3QpKQogICAgICAgICAgICAgICAgICAgKGxlZnQgMCkKICAgICAgICAgICAgICAgICAgIChyaWdodCBpKSkKCiAgICAgICAgICAgICAgIDs7INCR0LjQvdCw0YDQvdGL0Lkg0L/QvtC40YHQuiDQv9C+0LfQuNGG0LjQuCDQtNC70Y8g0LLRgdGC0LDQstC60LgKICAgICAgICAgICAgICAgKGxvb3Agd2hpbGUgKDwgbGVmdCByaWdodCkKICAgICAgICAgICAgICAgICAgICAgZG8gKGxldCAoKG1pZCAoZmxvb3IgKCsgbGVmdCByaWdodCkgMikpKQogICAgICAgICAgICAgICAgICAgICAgICAgIChpZiAoZnVuY2FsbCBjbXAga2V5IChudGggbWlkIGxpc3QpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoc2V0ZiByaWdodCBtaWQpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChzZXRmIGxlZnQgKDErIG1pZCkpKSkpCgogICAgICAgICAgICAgICA7OyDQodC00LLQuNCzINGN0LvQtdC80LXQvdGC0L7QsiDQstC/0YDQsNCy0L4sINGH0YLQvtCx0Ysg0L7RgdCy0L7QsdC+0LTQuNGC0Ywg0LzQtdGB0YLQvgogICAgICAgICAgICAgICAobG9vcCBmb3IgaiBmcm9tIGkgZG93bnRvICgxKyBsZWZ0KQogICAgICAgICAgICAgICAgICAgICBkbyAoc2V0ZiAobnRoIGogbGlzdCkgKG50aCAoMS0gaikgbGlzdCkpKQoKICAgICAgICAgICAgICAgOzsg0JLRgdGC0LDQstC60LAg0Y3Qu9C10LzQtdC90YLQsAogICAgICAgICAgICAgICAoc2V0ZiAobnRoIGxlZnQgbGlzdCkga2V5KSkpKQogIGxpc3QpCgo7OyDQpNGD0L3QutGG0LjRjyDQtNC70Y8g0YLQtdGB0YLQuNGA0L7QstCw0L3QuNGPICjQv9GA0LjQvNC10YAg0LjRgdC/0L7Qu9GM0LfQvtCy0LDQvdC40Y8gbnVtLWNtcCkKKGRlZnVuIHRlc3QtYmluYXJ5LWluc2VydGlvbi1zb3J0ICgpCiAgKGxldCAoKHRlc3QtbGlzdCAobGlzdCA1IDIgOCAxIDkgNCkpKQogICAgKGZvcm1hdCB0ICJPcmlnaW5hbCBsaXN0OiB+YX4lIiB0ZXN0LWxpc3QpCiAgICAobGV0ICgoc29ydGVkLWxpc3QgKGJpbmFyeS1pbnNlcnRpb24tc29ydCAoY29weS1saXN0IHRlc3QtbGlzdCkgIydudW0tY21wKSkpIDsg0JLQsNC20L3QvjogY29weS1saXN0CiAgICAgIChmb3JtYXQgdCAiU29ydGVkIGxpc3Q6ICAgfmF+JSIgc29ydGVkLWxpc3QpKSkpCgo7OyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KOzsg0KLQtdGB0YLQuNGA0L7QstCw0L3QuNC1CihsZXQqICgodGVzdC1zaXplIDEwMCkgOyDQoNCw0LfQvNC10YAg0YHQv9C40YHQutCwINC80L7QttC90L4g0LzQtdC90Y/RgtGMCiAgICAgICAodGVzdC1kYXRhIChnZW5lcmF0ZS1yYW5kb20tbGlzdCB0ZXN0LXNpemUpKSkgOyBSZW1vdmVkIHVubmVjZXNzYXJ5IGNvcHkKICAoZm9ybWF0IHQgItCY0YHRhdC+0LTQvdGL0LUg0LTQsNC90L3Ri9C1ICjQv9C10YDQstGL0LUgMTAg0Y3Qu9C10LzQtdC90YLQvtCyKTogfmEuLi5+JSIgKHN1YnNlcSB0ZXN0LWRhdGEgMCAobWluIDEwIChsZW5ndGggdGVzdC1kYXRhKSkpKQoKICAoZm9ybWF0IHQgIn4l0KHQvtGA0YLQuNGA0L7QstC60LAg0KjQtdC70LvQsDp+JSIpCiAgKHRpbWUgKHNoZWxsLXNvcnQgKGNvcHktbGlzdCB0ZXN0LWRhdGEpICMnbnVtLWNtcCkpIDsg0KHQvtC30LTQsNC10Lwg0LrQvtC/0LjRjiDQv9C10YDQtdC0INGB0L7RgNGC0LjRgNC+0LLQutC+0LkKCiAgKGZvcm1hdCB0ICJ+JdCh0L7RgNGC0LjRgNC+0LLQutCwINCx0LjQvdCw0YDQvdGL0LzQuCDQstGB0YLQsNCy0LrQsNC80Lg6fiUiKQogICh0aW1lIChiaW5hcnktaW5zZXJ0aW9uLXNvcnQgKGNvcHktbGlzdCB0ZXN0LWRhdGEpICMnbnVtLWNtcCkpKSA7INCh0L7Qt9C00LDQtdC8INC60L7Qv9C40Y4g0L/QtdGA0LXQtCDRgdC+0YDRgtC40YDQvtCy0LrQvtC5Cgo7OyDQl9Cw0L/Rg9GB0Log0YLQtdGB0YLQsAoodGVzdC1iaW5hcnktaW5zZXJ0aW9uLXNvcnQp