[Python-Dev] Sorting

[Tim Peters]

If you have access to a good library, you'll enjoy reading the original
paper on samplesort; or a scan can be purchased from the ACM:

    Samplesort:  A Sampling Approach to Minimal Storage Tree Sorting
    W. D. Frazer, A. C. McKellar
    JACM, Vol. 17, No. 3, July 1970

As in many papers of its time, the algorithm description is English prose
and raises more questions than it answers, but the mathematical analysis is
extensive.

Two things made me laugh out loud:

1. The largest array they tested had 50,000 elements, because that
   was the practical upper limit given storage sizes at the time.
   Now that's such a tiny case that even in Python it's hard to
   time it accurately.

2. They thought about using a different sort method for small buckets,

      However, the additional storage required for the program would
      reduce the size of the input sequence which could be accommodated,
      and hence it is an open question as to whether or not the
      efficiency of the total sorting process could be improved in
      this way.

In some ways, life was simpler then <wink>.

for-example-i-had-more-hair-ly y'rs  - tim