9

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?

Improve this question
5
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 14:42
  • Apparently, it's better than Quickest ?
    – JeffO
    Jun 28, 2013 at 18:42

3 Answers 3

Reset to default
13

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.

Improve this answer
4
  • 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, 2013 at 14:37
  • 1961, Algorythm 64 : Quicksort
    – Pieter B
    Jun 28, 2013 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, 2013 at 1:46
  • 3
    @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, 2014 at 3:36
0

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.

Improve this answer
-1

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

Improve this answer

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