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 23

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, so the program came with a guarantee. Algorithm 63, Partition, does the work. Algorithm 64 is only the eight lines above, but they are the lines people remember. It appeared in the algorithms section of Communications of the ACM, between Partition and Algorithm 65, Find.

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