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

Question

in book algorithm in c++ by robert sedgewick 

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

Answer 1

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

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

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

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

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

, то это 4л/к .... до кп/к

так что (2 + 4 + ... к) * (п/к) который является log2 (k)

поэтому этот шаг log2 (к) * (п/к)

так, порядок алгоритма (п/к) журнал (п/к) + log2 (к) * (п/к)