Calculating the Complexity of a Two Part Algorithm

Question

This is in relation to this post I made. I eventually solved this by the following approach:

1. Take the un-ordered file with all the purchasing data and use the UNIX sort utility to order the file on the customer identifier. Since the file can be 500 million lines (and grows over time) I used the -T option and directed the utility to use my hard drive to carry out it's sorting computation. The sort utility uses external sort to do the sorting.
2. I created a program which took this ordered file and in one pass computed the required values (a single for-loop, no nested for-loops)

Step 2 is O(n) clearly. But what about Step 1? What is the complexity here and more to the point of the question, what is the overall complexity of this two-stage solution?

• Yuval Filmus: The answer might depend on the algorithm that sort uses for "external sorting", whatever that means.
• C.S: @YuvalFilmus vkundeti.blogspot.com/2008/03/… - the post says it is Ω((N/M)log(N/M)/log(R)). But how do I use this to compute the overall complexity?
• Yuval Filmus: Presumably you’re interested in an upper bound on the time complexity. Also, you haven’t stated what $M$ and $R$ are.
• D.W.: en.wikipedia.org/wiki/External_sorting
• C.S: @YuvalFilmus , N is the size of the data to sort in bytes and M is the amount of main memory on the machine (RAM). Yes, I am interested in the upper bound on the time complexity. The question really is what is the procedure to work out the overall complexity of two different algorithms combined together