plist sorting

sort-plist.lisp

;;; Copyright github.com/goose121, released under CC0

(defun sort-plist (plist &key (test #'<) (key #'cadr))
  (labels
      ((split (plist)
         (loop :for half :on (cdr plist) :by #'cddr
               :for whole :on (cddddr plist) :by #'cddddr
               :finally (return (values plist (shiftf (cdr half) nil)))))
       (plist-merge (p1 p2)
         (loop :with res =
                         (cond
                           ((not p1) p2)
                           ((not p2) p1)
                           ((funcall test (funcall key p2) (funcall key p1))
                            (shiftf p2 (cddr p2)))
                           (t (shiftf p1 (cddr p1))))
               :with acc = res
               :while (and p1 p2)
               :do (if (funcall test (funcall key p2) (funcall key p1))
                       (shiftf (cddr acc) p2 (cddr p2))
                       (shiftf (cddr acc) p1 (cddr p1)))
                   (setf acc (cddr acc))
               :finally
                  (setf (cddr acc) (or p1 p2))
                  (return res)))
       (inner (plist len)
         (if (cddr plist)
             (multiple-value-bind (l1 l2) (split plist)
               (plist-merge
                (inner l1 (ceiling len 2))
                (inner l2 (floor len 2))))
             plist)))
    (inner plist (length plist))))