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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4