Quicksort (1961) [pdf] | Hacker News Reader

Quicksort (1961) [pdf]

cs.ox.ac.uk

80 pointsjpelecanos20 comments

It's fascinating that this is only six pages long. The complexity analysis and corresponding math is sufficiently light as to be both straightforwardly comprehensible and inline with the body of the paper (instead of thrown into a "Theorem Appendix" at the end). The entire paper is exceptionally readable.

In contrast, new research that could be called "fundamental" in algorithms and theoretical computer science is typically several times longer and more complex. On one hand it seems intuitive that the more mature a field is, the higher the prerequisites for review and contribution. Computer science papers from the 60s seem much easier to read these days that what's been put out in the JACM since 2000, and modern papers in pure mathematics research are dense and incomprehensible (and commensurately more difficult to publish results in) even when placed next to modern research in computer science.

On the other hand, a fundamental improvement to Quicksort was developed in 2009 and the author's paper comes in only five pages [1]. Is that because the improvement is "minor", because the author is exceptional at explaining the fundamental ideas clearly and succinctly, or because the author was relatively lazy about putting in the things usually demanded for publication (long sections on methodology, historical context, problem motivation, complexity analysis in different implementation contexts...)? It's hard to know whether some of these academic papers actually require their significant length, or if the presentation of material is simply inefficient. Cuckoo hash [2] was developed in 2001, but its paper comes in at 26 pages despite it being a fairly intuitive construction. The authors didn't just explain the fundamental result, they included two full pages of reference citations, a section on empirical performance characteristics and complete details of their experimental lab setup.

I'm not advocating that modern papers should necessarily be shorter, but I think it's an interesting question.

__________________________

1. http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuic...

2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25....

This is why, when new to a subject area, I prefer reading older papers before trying to read anything recent.

Gratuitous complexity builds over time. (And there is no subject area where I have seen such gratuitous complexity as with computers.)

I have always thought this was because either authors assume knowledge of the earlier papers and/or they have become "too familiar" with the concepts, but I could be wrong. In the later case, perhaps an analogy would be a singer who has to perform the same song thousands of times. When an artist sings it for the 999th time it may sound different and maybe there is assumption everyone has heard it before.

Whatever the reason, it is common to see the fundamental concepts either glossed over or not even mentioned in recent papers.

The exception to this, for me, where subsequent papers are helpful, is when they succinctly summarise prior research or track a subject area over time, e.g., annual reviews.

Anyway, when I am searching for older papers, it often feels "counterintuitive" since I see many people studying an area for the first time who want only the latest research. Perhaps an analogy here could be software. There seems to be a fascination on HN with software that is "new" and being changed on a daily basis versus software that is finished and has been in use for a long time.

A related idea is university textbooks. Many students believe they must have the latest editions, for a variety of reasons. However the changes from one edition to the next may be relatively small and easily summarized. IME, sometimes a topic may be more clearly explained in earlier editions. Reading the earlier edition's treatment of a topic followed by the later edition's treatment is sometimes illuminating in ways that reading only the latest edition is not.

In summary, I find it easier to read the old, 1-3 page paper that lucidly discloses an original concept and then build understanding from there, reading subsequent research, than to read something written, e.g., this year and assume that old research, by virtue of it date, is just a minor detail and no longer important.

Right. I've noticed in multiple areas of science that often the pioneers of some technique/theory knew how to do it properly, but lacked the right computational, or other, technology, and had to fudge it in some way they were clear about, but others aren't. People then persist with that unsatisfactory approach, or data produced with it, long after they shouldn't. Reading the original work is definitely worth risking a little wasted time.

Lazy is often succinct.

Well of course there’s more citations 40 years in - there’s a lot of prior work that deserves credit!

Your [1] example is hardly going to be considered a paper in a publishable state. The mathematical investigations aren’t present, and the full source code is too much.

Your article [1] isn't a real published article, and it doesn't have a proper analysis. For somebody who has actually done the work, and gotten it published, see https://arxiv.org/pdf/1303.5217.pdf

While the analysis in your [1] above is plainly wrong, the algorithm started a long work of (traditional) research. The Ph.d. thesis [1] has a great summary on the impact of your [1].

For Cuckoo hashing, the original publication might be difficult to digest, but the journal version [2] improved it already quite a bit. There is a great explanation with an actual analysis by one of its original inventors available at [3]. It usually takes a long time to find the best way of describing an algorithm and showing why it works.

1. http://wild-inter.net/publications/wild-2016.pdf

2. http://www.itu.dk/people/pagh/papers/cuckoo-jour.pdf

3. http://www.itu.dk/people/pagh/papers/cuckoo-undergrad.pdf

I had the pleasure of attending a talk by Tony Hoare when I was at Microsoft in 2007. He was a staff member at Microsoft research UK and was visiting the Redmond campus. Having studied and appreciated quick sort in freshman CS it was like being in the presence of God :)

Tony was 27 when he came up with QuickSort. Impressive

Quicksort should be the first sort you try on your rando dataset. The native search implementation is nearly always competitive with the best algorithm for your particular lunch. And it can be tweaked to specialize on datasets.

How can you tweak it to specialize?

Probably on how you select your pivot.

> The native search implementation is nearly always competitive with the best algorithm for your particular lunch.

Did you mean "The native sort implementation"? Also "lunch"?

Interestingly there is no pseudo code describing the solution.

There's a reference to a paper that contains ALGOL code instead.

Quicksort is great, but the name is not great. It would have been better named as 'partition sort'.

6:47 minutes to sort 2k items.

We've come a long way. Python isn't even the fastest of languages

  $ time python3.6 -c "import random; l = random.choices(range(1_000_000), k=2_000); l.sort()"
  
  real	0m0.033s

... and this also takes into account creating the 2k random ints.

And Python doesn’t even use quicksort any more.

Nice find, bookmarked for nostalgia (even tho I wasn't born yet).

Reply on news.ycombinator.com