Best sort for multi threaded application

Question

Today in a interview I have got the question asking which sort you use for multi threaded application.Weather it is a merge sort or quick sort.

Answer 1

Every divide and conquer algorithm can be quite easily parallelised. Merge sort and quicksort both follow the same basic schema which can be run in parallel:

procedure DivideAndConquer(X)
  if X is a base case then
    Process base case X
    return

  Divide X into [Y0 … Yn[
  for Y ∈ [Y0 … Yn[ in parallel do
    DivideAndConquer(Y)

  Merge [Y0 … Yn[ back into X

Where they differ is that in quicksort, the division is difficult and merging is trivial (no operation). In merge sort, it’s the other way round: dividing is trivial and merging is difficult.

If you implement the above schema, quicksort is actually easier to parallelise because you can just forget about the merge step. For merge sort, you need to keep track of finished parallel tasks. This screws up the load balancing.

On the other hand, if you follow the above schema, you’ve got a problem: the very first division, and the very last merging, will only use a single processor and all other processors will be idle. Thus it makes sense to parallelise these operations as well. And here we see that parallelising the partitioning step in quicksort is much harder than parallelising the merge step in merge sort.

Answer 2

You use merge sort for multi-threaded applications.

The reason:

Merge sort divides the problem into separate smaller problems (smaller arrays) and then merges them. That can be done in separate threads.

Quick sort does a pivot sort on a single array, so it's harder to divide the problem efficiently between threads.