Есть файл большого размера (нельзя загрузить в оперативную память). Его нужно отсортировать побайтно. Причем число операций чтения допускается порядка O(NlogN), а число записей порядка O(N).
Как правило предлагается qsort, но ему необходимо O(NlogN) чтений и записей.
Были бы интересны любые идеи.