Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The point of this question is not to debate the merits of this over any other sorting algorithm - certainly there are many other questions that do this. This question is about the name. Why is Quicksort called "Quicksort"? Sure, it's "quick", most of the time, but not always. The possibility of degenerating to O(N^2) is well known. There are various modifications to Quicksort that mitigate this problem, but the ones which bring the worst case down to a guaranteed O(n log n) aren't generally called Quicksort anymore. (e.g. Introsort).

I just wonder why of all the well-known sorting algorithms, this is the only one deserving of the name "quick", which describes not how the algorithm works, but how fast it (usually) is. Mergesort is called that because it merges the data. Heapsort is called that because it uses a heap. Introsort gets its name from "Introspective", since it monitors its own performance to decide when to switch from Quicksort to Heapsort. Similarly for all the slower ones - Bubblesort, Insertion sort, Selection sort, etc. They're all named for how they work. The only other exception I can think of is "Bogosort", which is really just a joke that nobody ever actually uses in practice. Why isn't Quicksort called something more descriptive, like "Partition sort" or "Pivot sort", which describe what it actually does? It's not even a case of "got here first". Mergesort was developed 15 years before Quicksort. (1945 and 1960 respectively according to Wikipedia)

I guess this is really more of a history question than a programming one. I'm just curious how it got the name - was it just good marketing?

share|improve this question
1  
Timsort, which is improved quicksort, does not take name after how it works, but rather from it's inventor. Names like flashsort or introsort don't tell you much about algorithm either. –  vartec Jun 28 '13 at 14:23
    
What's in a name? that which we call a rose By any other name would smell as sweet; That or be just as fast. Besides, the possibility of degenerating to O(N^2) has a small chance of happening, and N LogN is pretty good for an algorithm, despite the fact that we have faster algorithms today. Besides, by the time something faster came up, it was too late, everyone already called it Quicksort! –  Ampt Jun 28 '13 at 14:33
1  
@vartec Timsort is actually derived from Mergesort, not Quicksort, but I'll agree, that's another exception. Introsort doesn't give you the whole algorithm, but it at least describes something of how it works - it's "introspective". Flashsort I'm not very familiar with, but I guess it's called that because it "flashes" each element into its best guess of where it should be? –  Darrel Hoffman Jun 28 '13 at 14:37
1  
@Ampt Actually, in Quicksort's most basic form, the O(N^2) case is quite likely in the common case where the data is already sorted or nearly so. Admittedly, later developments such as Median-of-3 or random pivot make it far more rare, but the name is still used for implementations which lack such improvements. –  Darrel Hoffman Jun 28 '13 at 14:42
    
Apparently, it's better than Quickest ? –  JeffO Jun 28 '13 at 18:42

3 Answers 3

up vote 10 down vote accepted

In 1962 research on sorting algorithms wasn't as far advanced as today and the computer scientist Tony Hoare found a new algorithm which was quicker than the other so he published a paper called Quicksort and as the paper was quoted the title stayed.

Quoting the abstract:

A description is given of a new method of sorting in the random-access store of a computer. The method compares very favourably with other known methods in speed, in economy of storage, and in ease of programming. Certain refinements of the method, which may be useful in the optimization of inner loops, are described in the second part of the paper.

share|improve this answer
    
Footnote on page 11 in the linked PDF suggests there was an earlier paper on Quicksort published in 1961. That paper is also mentioned in the References section at the end of the paper. –  FrustratedWithFormsDesigner Jun 28 '13 at 14:37
    
1961, Algorythm 64 : Quicksort –  Pieter B Jun 28 '13 at 14:40
    
I guess this is as close to the correct answer as I'm likely to get. It explains who named it, but not why it's still using that name, when more recent and potentially quicker alternatives exist. Good read - it's interesting to see how much stuff from back in the 60's still applies to modern technology. –  Darrel Hoffman Jun 30 '13 at 1:46
    
@DarrelHoffman Why would the name change? At what point would the drawbacks of calling the algorithm Quicksort outweigh the cost of trying to get everyone to call it PartitionSort or whatever? –  prosfilaes Feb 4 at 3:36

I believe it's because, at the time it was invented, it was very much quicker than all (or, rather, most, as speed also depends heavily on the kind of data and in some cases other algorithm become much faster than quicksort) of the algorithms out there.

So yes, it's historical (I don't know precisely that history, however...)

But I agree that its name should instead contain a hint of the algorithm...

share|improve this answer

I believe that it was originally called Hoare Sort after the inventor but the name got changed fairly early due to Hoare sounding a little to close to whore in English. As to why they chose "quick" instead of something else, I'm not sure.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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