parallel sorting methods

Question

in book algorithm in c++ by robert sedgewick

there is such kind of problem how many parallel steps would be required to sort n records that are distributed on some k disks(let say k=1000 or any value ) and using some m processors the same m can be 100 or arbitrary number i have questions what we should do in such case? what are methods to solve such kind of problems? and what is answer in this case?

Answer 1

Well, initially you divide the n records over k disks and sort them. Assuming you use an n Log(n) sort, this will take (n/k)log(n/k) time.

Then, you have to merge the sorted lists. You can do this in parallel. Each merge step will take o(length of list).

Initially the length of the lists are n/k, and at the end the length is 1.

So this will take

2n/k (have to merge each pair of n/k lists into a single list size 2n/k)

then it's 4n/k .... up to kn/k

so it's (2 + 4 + ... k) * (n/k) which is log2(k)

so this step is log2(k) * (n/k)

so order of algorithm is (n/k)log(n/k) + log2(k) * (n/k)