Nested sorting class of array sorting algorithms

[ttw]

This is equivalent (in the general case) to one of the merge sorts. These are as efficient as it gets with comparison based sorting. The binary version sorts a bunch of short arrays (or buckets) by whatever method is efficient for short arrays. Then the arrays are merged pairwise to grow their lengths. (If the starting arrays are differing size, merging from the smallest is best. This isn't usually mentioned.)