I think that the trick here is to use some sort of a divide and conquer sorting algorithm (such as merge sort or quick sort) and use this idea to divide the sorting between several computers so if you have p computers it will take O(n/p*log(n/p)) The problem arises when you need to merge all the data together back to a big array, but that only takes O(n) since the sub-arrays are already sorted. The big con to this is that merge sort (the traditional method) requires extra memory for each iteration, so its possible to use merge sort to divide the array to p computers but in each computer use quick sort (which is in place sorting) to sort the sub-arrays. that way you save the memory (since you need to move the sub-arrays to other computer anyway) and still get sorting of O(n/plog(n/p))

16