4 ms·
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
by Perceval 16y ago
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.
Is this plausible? Has this been done already?
- foob 16y agoThis 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.3117 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.
- anonymoushn 16y agoThis 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.
- T-hawk 16y agoI'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.