I need to add a single integer to a list that's already sorted, such that it goes in the right place. My first tought was something like

(sort (cons newelt list) #'<)

However, given that list is already sorted, only one insertion is really needed, which means this solution could be horribly unsuitable depending on the algorithm used by sort.

So, which is the algorithm that sort uses?

Would I be better off doing something like the following?

(let ((tail list))
  ;; The first element is never less-than
  (while (and tail (< newelt (cadr tail)))
    (setq tail (cdr tail)))
  (setcdr tail (cons newelt (cdr tail)))
  list)