Hacker News new | past | comments | ask | show | jobs | submit login

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.

Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact