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!
After the sorting phase the merge phase processes m runs in parallel therefore you get the base m = M/B.
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.
