procedure quicksort (A,M,N); value M,N;
            array A; integer M,N;
begin    integer I,J;
         if M < N then begin partition(A,M,N,I,J);
                             quicksort(A,M,J);
                             quicksort(A,I,N);
                       end
end      quicksort

3 of 20

Algorithm 64: Quicksort

C. A. R. Hoare, 1961

ALGOL 60, as printed in Communications of the ACM 4(7)

Hoare invented Quicksort in 1959 but could not write it down cleanly until he learned ALGOL 60 at a 1961 course in Brighton taught by Naur, Dijkstra, and Landin. ALGOL allowed recursion, and recursion was the whole shape of the idea: pick an element, partition the array around it, and sort the two sides the same way.

The sort needs no extra memory, which mattered when a whole machine held a few thousand words, and Hoare proved its average cost was proportional to n log n, pairing a practical program with a mathematical guarantee. Algorithm 63, Partition, does the work; Algorithm 64 is only the eight lines above, but they are the lines people remember. The published algorithms column of the ACM, where this appeared, was the open-source repository of its day: short, reviewed, and free to copy by hand.

Source: doi.org
Rights: Excerpt from Communications of the ACM 4(7), ACM 1961; reproduced for commentary