Можно ли сортировать файл на нескольких компах одновременно?

Question

[wanomgn]

Есть огромный файл.. Сортировка на одном компе происходит около суток.
Существуют ли способы распаралелить эту сортировку на несколько компов?

Answer 1

[Александр Паньшин]

MergeSort. Разбить файл на несколько, отсортировать каждый часть по отдельности, а потом смержить. У мержа сложность будет O(n), где n - длина исходного массива.

Comments

[Sergey Lerg]

С O(n) вы переборщили. У него O(n log n). Отличительная черта MergeSort в том, что он мало зависит от входных данных и сложность остаётся на одном уровне.

[Александр Паньшин]

У всего алгоритма - да, n log(n). Я написал сложность именно стадии merge.

[Sergey Lerg]

Тогда понятно.

[wanomgn]

Разбил файл на 10 кусков. Отсортировал каждый по отдельности.. А чем их "смержить?" Все крутится под linux. У команды sort есть режим merge (sort -m), но получается что 10 сортированных кусков просто собрались в один файл который естественно не отсортирован.

[Power]

@wanomgn: Вы не правы. sort -m делает именно то, что нужно (я только что проверил). Возможно, у вас на машинах разные локали и из-за этого сортируется неправильно. Или вы неправильно вызываете sort.

[wanomgn]

@Power: да. действительно. я тупил. огромное спасибо.

Answer 2

[Николай]

MPI-подобные системы вам в помощь.