; bubble sort begin
(defun bubble_sort (lst)
    (if (<= (length lst) 1)
        (return-from bubble_sort lst))

    (loop for i from 0 to (- (length lst) 2)
        do (
            if (> (elt lst i) (elt lst (+ i 1)))
            (rotatef
                (elt lst i)
                (elt lst (+ i 1))
            )
        )
    )

    (return-from bubble_sort
        (append
            (bubble_sort
                (subseq lst 0 (- (length lst) 1))
            )
            (last lst)
        )
    )
)

(write (bubble_sort '(1 3 15 4 5 3 7 2 21 13 12 1 -1)))
(terpri)
(write (bubble_sort '(15 4 5)))
(terpri)
(write (bubble_sort '(15 4)))
(terpri)
(write (bubble_sort '(15)))
; bubble sort end

; merge sort begin
(defun merge_sort (lst)
  (defun merge_lists (list1 list2)
    (cond
      ((= (length list1) 0) list2)
      ((= (length list2) 0) list1)
      ((< (car list1) (car list2))
        (append
          (list (car list1))
          (merge_lists (cdr list1) list2)
        )
      )
      ((> (car list1) (car list2))
        (append
          (list (car list2))
          (merge_lists (cdr list2) list1)
        )
      )
      ((= (car list1) (car list2))
        (append
          (list (car list1) (car list2))
          (merge_lists (cdr list1) (cdr list2))
        )
      )
    )
  )

  (let ((len (length lst)))
    (cond
      ((<= len 1) lst)
      (t
        (merge_lists
          (merge_sort (subseq lst 0 (ceiling (/ len 2))))
          (merge_sort (subseq lst (ceiling (/ len 2))))
        )
      )
    )
  )
)

(write (merge_sort '(1 3 15 4 5 3 7 2 21 13 12 1 -1)))
(terpri)
(write (merge_sort '(15 4 5)))
(terpri)
(write (merge_sort '(15 4)))
(terpri)
(write (merge_sort '(15)))
; merge sort end