MergeSort. Разбить файл на несколько, отсортировать каждый часть по отдельности, а потом смержить. У мержа сложность будет O(n), где n - длина исходного массива.
С O(n) вы переборщили. У него O(n log n). Отличительная черта MergeSort в том, что он мало зависит от входных данных и сложность остаётся на одном уровне.
Разбил файл на 10 кусков. Отсортировал каждый по отдельности.. А чем их "смержить?" Все крутится под linux. У команды sort есть режим merge (sort -m), но получается что 10 сортированных кусков просто собрались в один файл который естественно не отсортирован.
@wanomgn: Вы не правы. sort -m делает именно то, что нужно (я только что проверил). Возможно, у вас на машинах разные локали и из-за этого сортируется неправильно. Или вы неправильно вызываете sort.
