What algorithm is used for the sort function in Common Lisp?

Question

I think this may be implementation dependent, so the question is not entirely correct. It still looks like some sort of comparative variety with n (log n) medium complexity. To rephrase my question in a more accountable way: is there any reason for writing my own quick sort or merge sort, or any other comparison other than didactic?

Answer 1

Yes, an algorithm is an implementation defined (imagine that you define a specific algorithm in the standard, and then someone comes in long and invents a more general one). You can find the standard yourself (just google clhs sort).

The implementation provided by sort and stable-sort , as a rule, should cover almost any sort you need. I can imagine the following reasons to write my own:

• You need interceptors at certain stages of the sorting procedure.
• You only need partial sorting
• You need a specific algorithm for your problem area.
• Do you want to compare different algorithms

In any case, I should recommend a deep study of existing sorting implementations so as not to miss possible optimizations (which usually matters in the context of sorting).