# What algorithm does sort use?

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)
``````
• I'd use a binary heap (e.g. heap.el), if that was a frequent operation in my code.
– user227
Nov 19 '14 at 14:29
• Let `B` be initial already sorted `list` and `A` and `C` initially empty lists. Split `B` in two parts `B1`, `B2` of lengths `m` and `m` or `m+1` and `m`, compare `newelt` to first element of `B2`. If `newelt` is `≥` extend `A` to its right with `B1` and replace `B` with `B2`, else extend `C` to its left with `B2` and replace `B` with `B1`. After `O(log n)` such steps nothing is left in `B`. Then `A` contains the things `≤ newelt`, and `C` those `> newelt`, and concatenation produces the extended sorted list. Apologies for not very `e-lisp` like language.
– jfbu
Nov 30 '14 at 8:48

If you have the Emacs source code installed, you can find the source code for `sort` with `M-x find-function`.
There you can see that `sort` performs a merge sort. It checks the length of the list, breaks the list into half, sorts the "front" and the "back" parts separately through recursion, and then merges the two.
As for whether your implementation would be faster — measure it! It is more efficient in theory (O(n) vs O(n log n)), but `sort` has the advantage of being written in C, so the result might go either way. (Of course, don't forget to byte-compile your function.)