методы параллельной сортировки

Question

in book algorithm in c++ by robert sedgewick

есть такая проблема сколько параллельных шагов потребуется для сортировки n записей, которые распределены по некоторым k дискам (скажем, k = 1000 или любое значение), и с использованием нескольких m процессоров один и тот же m может быть 100 или произвольным числом у меня есть вопросы что мы должны делать в таком случае? Какие методы для решения таких проблем? и каков ответ в этом случае?

Answer 1

Ну, сначала вы делите n записей на k дисков и сортируете их. Предполагая, что вы используете n Log (n) сортировку, это займет (n / k) log (n / k) время.

Затем вы должны объединить отсортированные списки. Вы можете сделать это параллельно. Каждый шаг слияния будет занимать o (длина списка).

Первоначально длина списков равна n / k, а в конце длина равна 1.

Так что это займет

2n / k (необходимо объединить каждую пару списков n / k в один список размером 2n / k)

тогда это 4n / k .... до kn / k

так что это (2 + 4 + ... k) * (н / к) который log2 (k)

так что этот шаг log2 (k) * (н / к)

так что порядок алгоритма (n / k) log (n / k) + log2 (k) * (n / k)