If you have a k sorted (or reverse sorted) blocks, you can get O(n log k) performance in merge sort variants. Especially, if k is a small fixed constant, like 1 or 2 or 10, you should get linear performance.

A few language's standard library sorts implement that already.

For a serious implementation, of course, you not only care about the asymptotic performance, but also absolute runtimes.