Complexity of external merge sort

What is the complexity of a 2 phase multi-wa开发者_JS百科y external sort using quick sort (nlogn) as internal sort.

Not an expert here but...

If I understand correctly, what you describe as phases are the number of passes your algorithm will make over the input, right? In this case, a running time approximation would be the number of passes (2 in your case) * the time necessary to read and write the whole input to the external device.

When evaluating complexity of such algorithms it is hard to put it in usual running time terms. There are many aspects that could influence the result (sequential/non-sequential access, technology, etc). The common approach is to provide complexity in terms of passes, which accounts from the number of devices used, the number of items in the input, and the number of items that can fit in memory.

The point is that the sorting algorithm is dominated by the IO operations. Internal quick sort should be ok (although its quadratic worst case).

Also, I'm not sure if you counted the initial distribution. This is also a pass.