;;;Lisp strange version of mergesort
;;;written by Giovanni Santostefano
;;;http://santostefanogiovanni.blogspot.com

(defun g_merge(A B)
  "Merge 2 different lists"
  (cond 
   ((null A) B)
   ((null B) A)
   ((<= (first A) (first B)) (cons (first A) (g_merge (rest A) B)))
   (t (cons (first B) (g_merge A (rest B))))))

;;A is the list
;;I is the list half lenght
(defun g_firsthalf(A I)
  "Take the first half of a list"
  (if (= I 0)
      nil
    (cons (first A) (g_firsthalf (rest A) (- I 1)))))

;;A is the list
;;I is the list half length
(defun g_secondhalf(A I)
 "Take the second half of a list"
 (if (<= I 1)
     (rest A)
   (g_secondhalf (rest A) (- I 1))))

(defun g_mergesort(A)
  "The mergesort"
  (setq I (list-length A))
  ;(print A)
  (if (<= I 1) (return-from g_mergesort A))

  (setq M (round (/ I 2)))
  (setq C (g_mergesort (g_firsthalf A M))) ;blackbox
  ;(setq D (g_mergesort (g_secondhalf A M)));blackbox
  ;(g_merge C D) )
  (g_merge (g_mergesort (g_firsthalf A M)) (g_mergesort (g_secondhalf A M))) )