CODEWITHSUNDEEP
mergetime-complexityexternalmergesort
behiye.avci
behiye.avci

Reputation: 31

What is the complexity of external merge sort?

In wikipedia time complexity of external sort is given as follows

(N/B).log(M/B)(N/B)

where N is the total size of the data, M is memory size and B is the number of chunks in the memory. I can understand log part as we sort each chunk in RAM, however I could not understand the base of the log as M/B.

Any help would be appreciated!

Upvotes: 3

Views: 366

Answers (2)

rcgldr
rcgldr

Reputation: 28921

M is memory size and ...

The confusion is due to:

B is the number of chunks in the memory.

In the wiki article, B is the block size per chunk, so the number of chunks in the memory = M/B. The wiki time complexity is ignoring the fact that one of the chunks is used for merged output, and that the algorithm uses a k-way merge where k = (M/B)-1.

Upvotes: 0

Night Train
Night Train

Reputation: 2576

After the sorting phase the merge phase processes m runs in parallel therefore you get the base m = M/B.

Source: wikipedia.org/wiki/External_memory_algorithm

Upvotes: 1

Related Questions