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?
5
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.
4
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.
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…