;; Бинарный поиск позиции для вставки
(defun binary-search-pos (elem lst cmp)
  (labels ((binary-search (low high)
             (if (> low high)
                 low ; Найдена позиция для вставки
                 (let ((mid (floor (+ low high) 2)))
                   (if (funcall cmp elem (nth mid lst))
                       (binary-search low (1- mid)) ; Ищем в левой половине
                       (binary-search (1+ mid) high)))))) ; Ищем в правой половине
    (if (null lst)
        0 ; Если список пуст, позиция для вставки - 0
        (binary-search 0 (1- (length lst))))))
 
;; Вставка элемента в список на заданную позицию
(defun insert-at-pos (elem lst pos)
  (if (zerop pos)
      (cons elem lst) ; Вставляем в начало
      (if (null lst)
          (list elem) ; Если дошли до конца списка, а позиция не 0, вставляем в конец (для надежности)
          (cons (car lst) (insert-at-pos elem (cdr lst) (1- pos)))))) ; Рекурсивно двигаемся по списку
 
;; Основная функция сортировки бинарными включениями
(defun binary-insertion-sort (lst cmp)
  (if (null lst)
      nil ; Пустой список уже отсортирован
      (let* ((first-elem (car lst))
             (rest-sorted (binary-insertion-sort (cdr lst) cmp)) ; Рекурсивно сортируем остаток списка
             (pos (binary-search-pos first-elem rest-sorted cmp))) ; Находим позицию для вставки первого элемента
        (insert-at-pos first-elem rest-sorted pos)))) ; Вставляем первый элемент в отсортированный остаток
 
;; Примеры использования
;; Сортировка списка чисел по возрастанию
(let ((numbers '(5 2 8 1 9 4)))
  (format t "Original list: ~a~%" numbers)
  (let ((sorted-numbers (binary-insertion-sort numbers #'<)))
    (format t "Sorted list: ~a~%" sorted-numbers)))
 
;; Сортировка списка строк по алфавиту (лексикографически)
(let ((strings '("banana" "apple" "cherry" "date")))
  (format t "Original list: ~a~%" strings)
  (let ((sorted-strings (binary-insertion-sort strings #'string<)))
    (format t "Sorted list: ~a~%" sorted-strings)))
 
;; Сортировка списка чисел по убыванию (изменили функцию сравнения)
(let ((numbers '(5 2 8 1 9 4)))
  (format t "Original list: ~a~%" numbers)
  (let ((sorted-numbers (binary-insertion-sort numbers #'>)))
    (format t "Sorted list: ~a~%" sorted-numbers)))
 
;; Сортировка списка с использованием своей функции сравнения (по длине строки)
(defun compare-string-length (str1 str2)
  (< (length str1) (length str2)))
 
(let ((strings '("a" "bb" "ccc" "d")))
  (format t "Original list: ~a~%" strings)
  (let ((sorted-strings (binary-insertion-sort strings #'compare-string-length)))
    (format t "Sorted list: ~a~%" sorted-strings)))
 
;; Пример с пустым списком
(let ((empty-list '()))
  (format t "Original list: ~a~%" empty-list)
  (let ((sorted-list (binary-insertion-sort empty-list #'<)))
    (format t "Sorted list: ~a~%" sorted-list)))

Ozsg0JHQuNC90LDRgNC90YvQuSDQv9C+0LjRgdC6INC/0L7Qt9C40YbQuNC4INC00LvRjyDQstGB0YLQsNCy0LrQuAooZGVmdW4gYmluYXJ5LXNlYXJjaC1wb3MgKGVsZW0gbHN0IGNtcCkKICAobGFiZWxzICgoYmluYXJ5LXNlYXJjaCAobG93IGhpZ2gpCiAgICAgICAgICAgICAoaWYgKD4gbG93IGhpZ2gpCiAgICAgICAgICAgICAgICAgbG93IDsg0J3QsNC50LTQtdC90LAg0L/QvtC30LjRhtC40Y8g0LTQu9GPINCy0YHRgtCw0LLQutC4CiAgICAgICAgICAgICAgICAgKGxldCAoKG1pZCAoZmxvb3IgKCsgbG93IGhpZ2gpIDIpKSkKICAgICAgICAgICAgICAgICAgIChpZiAoZnVuY2FsbCBjbXAgZWxlbSAobnRoIG1pZCBsc3QpKQogICAgICAgICAgICAgICAgICAgICAgIChiaW5hcnktc2VhcmNoIGxvdyAoMS0gbWlkKSkgOyDQmNGJ0LXQvCDQsiDQu9C10LLQvtC5INC/0L7Qu9C+0LLQuNC90LUKICAgICAgICAgICAgICAgICAgICAgICAoYmluYXJ5LXNlYXJjaCAoMSsgbWlkKSBoaWdoKSkpKSkpIDsg0JjRidC10Lwg0LIg0L/RgNCw0LLQvtC5INC/0L7Qu9C+0LLQuNC90LUKICAgIChpZiAobnVsbCBsc3QpCiAgICAgICAgMCA7INCV0YHQu9C4INGB0L/QuNGB0L7QuiDQv9GD0YHRgiwg0L/QvtC30LjRhtC40Y8g0LTQu9GPINCy0YHRgtCw0LLQutC4IC0gMAogICAgICAgIChiaW5hcnktc2VhcmNoIDAgKDEtIChsZW5ndGggbHN0KSkpKSkpCgo7OyDQktGB0YLQsNCy0LrQsCDRjdC70LXQvNC10L3RgtCwINCyINGB0L/QuNGB0L7QuiDQvdCwINC30LDQtNCw0L3QvdGD0Y4g0L/QvtC30LjRhtC40Y4KKGRlZnVuIGluc2VydC1hdC1wb3MgKGVsZW0gbHN0IHBvcykKICAoaWYgKHplcm9wIHBvcykKICAgICAgKGNvbnMgZWxlbSBsc3QpIDsg0JLRgdGC0LDQstC70Y/QtdC8INCyINC90LDRh9Cw0LvQvgogICAgICAoaWYgKG51bGwgbHN0KQogICAgICAgICAgKGxpc3QgZWxlbSkgOyDQldGB0LvQuCDQtNC+0YjQu9C4INC00L4g0LrQvtC90YbQsCDRgdC/0LjRgdC60LAsINCwINC/0L7Qt9C40YbQuNGPINC90LUgMCwg0LLRgdGC0LDQstC70Y/QtdC8INCyINC60L7QvdC10YYgKNC00LvRjyDQvdCw0LTQtdC20L3QvtGB0YLQuCkKICAgICAgICAgIChjb25zIChjYXIgbHN0KSAoaW5zZXJ0LWF0LXBvcyBlbGVtIChjZHIgbHN0KSAoMS0gcG9zKSkpKSkpIDsg0KDQtdC60YPRgNGB0LjQstC90L4g0LTQstC40LPQsNC10LzRgdGPINC/0L4g0YHQv9C40YHQutGDCgo7OyDQntGB0L3QvtCy0L3QsNGPINGE0YPQvdC60YbQuNGPINGB0L7RgNGC0LjRgNC+0LLQutC4INCx0LjQvdCw0YDQvdGL0LzQuCDQstC60LvRjtGH0LXQvdC40Y/QvNC4CihkZWZ1biBiaW5hcnktaW5zZXJ0aW9uLXNvcnQgKGxzdCBjbXApCiAgKGlmIChudWxsIGxzdCkKICAgICAgbmlsIDsg0J/Rg9GB0YLQvtC5INGB0L/QuNGB0L7QuiDRg9C20LUg0L7RgtGB0L7RgNGC0LjRgNC+0LLQsNC9CiAgICAgIChsZXQqICgoZmlyc3QtZWxlbSAoY2FyIGxzdCkpCiAgICAgICAgICAgICAocmVzdC1zb3J0ZWQgKGJpbmFyeS1pbnNlcnRpb24tc29ydCAoY2RyIGxzdCkgY21wKSkgOyDQoNC10LrRg9GA0YHQuNCy0L3QviDRgdC+0YDRgtC40YDRg9C10Lwg0L7RgdGC0LDRgtC+0Log0YHQv9C40YHQutCwCiAgICAgICAgICAgICAocG9zIChiaW5hcnktc2VhcmNoLXBvcyBmaXJzdC1lbGVtIHJlc3Qtc29ydGVkIGNtcCkpKSA7INCd0LDRhdC+0LTQuNC8INC/0L7Qt9C40YbQuNGOINC00LvRjyDQstGB0YLQsNCy0LrQuCDQv9C10YDQstC+0LPQviDRjdC70LXQvNC10L3RgtCwCiAgICAgICAgKGluc2VydC1hdC1wb3MgZmlyc3QtZWxlbSByZXN0LXNvcnRlZCBwb3MpKSkpIDsg0JLRgdGC0LDQstC70Y/QtdC8INC/0LXRgNCy0YvQuSDRjdC70LXQvNC10L3RgiDQsiDQvtGC0YHQvtGA0YLQuNGA0L7QstCw0L3QvdGL0Lkg0L7RgdGC0LDRgtC+0LoKCjs7INCf0YDQuNC80LXRgNGLINC40YHQv9C+0LvRjNC30L7QstCw0L3QuNGPCjs7INCh0L7RgNGC0LjRgNC+0LLQutCwINGB0L/QuNGB0LrQsCDRh9C40YHQtdC7INC/0L4g0LLQvtC30YDQsNGB0YLQsNC90LjRjgoobGV0ICgobnVtYmVycyAnKDUgMiA4IDEgOSA0KSkpCiAgKGZvcm1hdCB0ICJPcmlnaW5hbCBsaXN0OiB+YX4lIiBudW1iZXJzKQogIChsZXQgKChzb3J0ZWQtbnVtYmVycyAoYmluYXJ5LWluc2VydGlvbi1zb3J0IG51bWJlcnMgIyc8KSkpCiAgICAoZm9ybWF0IHQgIlNvcnRlZCBsaXN0OiB+YX4lIiBzb3J0ZWQtbnVtYmVycykpKQoKOzsg0KHQvtGA0YLQuNGA0L7QstC60LAg0YHQv9C40YHQutCwINGB0YLRgNC+0Log0L/QviDQsNC70YTQsNCy0LjRgtGDICjQu9C10LrRgdC40LrQvtCz0YDQsNGE0LjRh9C10YHQutC4KQoobGV0ICgoc3RyaW5ncyAnKCJiYW5hbmEiICJhcHBsZSIgImNoZXJyeSIgImRhdGUiKSkpCiAgKGZvcm1hdCB0ICJPcmlnaW5hbCBsaXN0OiB+YX4lIiBzdHJpbmdzKQogIChsZXQgKChzb3J0ZWQtc3RyaW5ncyAoYmluYXJ5LWluc2VydGlvbi1zb3J0IHN0cmluZ3MgIydzdHJpbmc8KSkpCiAgICAoZm9ybWF0IHQgIlNvcnRlZCBsaXN0OiB+YX4lIiBzb3J0ZWQtc3RyaW5ncykpKQoKOzsg0KHQvtGA0YLQuNGA0L7QstC60LAg0YHQv9C40YHQutCwINGH0LjRgdC10Lsg0L/QviDRg9Cx0YvQstCw0L3QuNGOICjQuNC30LzQtdC90LjQu9C4INGE0YPQvdC60YbQuNGOINGB0YDQsNCy0L3QtdC90LjRjykKKGxldCAoKG51bWJlcnMgJyg1IDIgOCAxIDkgNCkpKQogIChmb3JtYXQgdCAiT3JpZ2luYWwgbGlzdDogfmF+JSIgbnVtYmVycykKICAobGV0ICgoc29ydGVkLW51bWJlcnMgKGJpbmFyeS1pbnNlcnRpb24tc29ydCBudW1iZXJzICMnPikpKQogICAgKGZvcm1hdCB0ICJTb3J0ZWQgbGlzdDogfmF+JSIgc29ydGVkLW51bWJlcnMpKSkKCjs7INCh0L7RgNGC0LjRgNC+0LLQutCwINGB0L/QuNGB0LrQsCDRgSDQuNGB0L/QvtC70YzQt9C+0LLQsNC90LjQtdC8INGB0LLQvtC10Lkg0YTRg9C90LrRhtC40Lgg0YHRgNCw0LLQvdC10L3QuNGPICjQv9C+INC00LvQuNC90LUg0YHRgtGA0L7QutC4KQooZGVmdW4gY29tcGFyZS1zdHJpbmctbGVuZ3RoIChzdHIxIHN0cjIpCiAgKDwgKGxlbmd0aCBzdHIxKSAobGVuZ3RoIHN0cjIpKSkKCihsZXQgKChzdHJpbmdzICcoImEiICJiYiIgImNjYyIgImQiKSkpCiAgKGZvcm1hdCB0ICJPcmlnaW5hbCBsaXN0OiB+YX4lIiBzdHJpbmdzKQogIChsZXQgKChzb3J0ZWQtc3RyaW5ncyAoYmluYXJ5LWluc2VydGlvbi1zb3J0IHN0cmluZ3MgIydjb21wYXJlLXN0cmluZy1sZW5ndGgpKSkKICAgIChmb3JtYXQgdCAiU29ydGVkIGxpc3Q6IH5hfiUiIHNvcnRlZC1zdHJpbmdzKSkpCgo7OyDQn9GA0LjQvNC10YAg0YEg0L/Rg9GB0YLRi9C8INGB0L/QuNGB0LrQvtC8CihsZXQgKChlbXB0eS1saXN0ICcoKSkpCiAgKGZvcm1hdCB0ICJPcmlnaW5hbCBsaXN0OiB+YX4lIiBlbXB0eS1saXN0KQogIChsZXQgKChzb3J0ZWQtbGlzdCAoYmluYXJ5LWluc2VydGlvbi1zb3J0IGVtcHR5LWxpc3QgIyc8KSkpCiAgICAoZm9ybWF0IHQgIlNvcnRlZCBsaXN0OiB+YX4lIiBzb3J0ZWQtbGlzdCkpKQ==