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

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.