For a while I've been wondering if the German Tank Problem could help make comparison sorts work better on large lists. Unfortunately, I lack the background to test whether this is true.
You wouldn't have to know the upper or lower bounds of the list, you could estimate them progressively from a smaller sample. Then you could insert each item to position N based on your distribution estimate. The further you get through the list, the better the distribution estimate would get, and inserting would get more accurate.
This isn't exactly what you're talking about but I think that it might interest you: Adaptive Data Partitioning Using Probability Distribution by Xipeng Shen, Yutao Zhong, and Chen Ding (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.31...). They estimate the probability distribution using a subset of the data and then use this to determine the partitions.
This seems like a more developed version of what Perceval had mentioned. Using German Tank Problem-based estimates would involve assuming a uniform distribution from the beginning.
I'm not aware of any general-purpose package for German Tank Sort, but it is sometimes implemented in specialized applications where you know a distribution is close to uniform. Run one round of estimating, then run bubble sort. The worst-case time of course is N², but if your estimator is sufficiently good and data is sufficiently uniform, you could possibly achieve an average time of fewer than log N passes through bubble sort so break the N log N barrier for your typical case.
A pretty useful collection. I've seen all these sorting algorithms depicted diagramatically previously, but having these all as a collection where you can change the data set and speed of rendering is pretty nice.
Would be a useful teaching aid IMO, as it quite poignantly demonstrates just how slow some of the 'intuitive' (for new programmers) sorting algorithms can be.
Pretty memorizing stuff right there. Makes me think of a more efficient way to compare all those lines and fit them into a more efficient order via a shorter algorithm. INtriguing.
Also maybe add introspective sort http://en.wikipedia.org/wiki/Introsort
I vaguely remember seeing something like this on HN before.
Ah, here we go http://www.sorting-algorithms.com/