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

Question

I guess, it might be implementation dependent, so the question isn't entirely correct. Still in looks like some kind of comparing sort with n(log n) average complexity. To rephrase my question in more answerable manner: is there any reason to write own quick sort or merge sort or any other comparing sort other then didactic?

Answer 1

Yes, the algorithm is implementation defined (imagine prescribing a specific algorithm in the standard, and then someone comes a long and invents a better general purpose one). You can look up the standard yourself (just google "clhs sort").

The implementation provided sort and stable-sort should generally cover almost any sorting need you have. I can imagine the following reasons to write your own:

• You need hooks into specific stages of the sorting procedure
• You need only partial sorting
• You need a specific algorithm for your problem domain
• You want to compare different algorithms

In any case, I should recommend to take a deep look into the existing sorting implementations in order not to miss possible optimizations (which is generally relevant in the context of sorting).