24

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)
  • 1
    I'd use a binary heap (e.g. heap.el), if that was a frequent operation in my code. – lunaryorn 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
26

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.)

  • @Malabarba For the record, what scale of lengths did you test it on? – T. Verron Nov 18 '14 at 16:24
  • 8
    Tested 1000 times inserting a random number to a list of 1000 random numbers (all pregenerated). The manual method was 6 times faster. – Malabarba Nov 18 '14 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.