How should you sort in this situation?

A master directory server receives a list of accounts, ordered by user ID, from each of several departmental directory servers. What's the best approach for this server to create a master list combining all the accounts ordered by user ID?

Questions you should ask:

1. Are the list of accounts from each individual server already sorted?
2. Can all the id's fit in memory?

Scenarios:

• Individual lists are not sorted 
• extra memory available
• You can pretty much just pick a sorting algorithm based on speed. Quick sort will do.
• extra memory not available
• You're still fine with most sorting algorithms as long as they're in-place (such as quicksort or selection sort). 
• Individual list are sorted
• extra memory available
• Merge sort can be very efficient here since the merge operation is O(n). Since we have extra memory, the auxiliary memory it needs may not be an issue. 
• extra memory not available
• You can still use merge sort if you lazy load the sublists. So instead of loading O(N) records in memory that will require an additional O(N) extra memory for the temporary buffer, you'll just have the O(N) temporary buffer and read the values of the sublists as you need them from either the disk or server. 

As you can see, there's no such thing as the"best" general sorting algorithm because it depends on what the constraints are!