Menu
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.
980
Quicksort lends itself to multithreading nicely. When you partition, one side of the partition sort in current thread, the other side sort in a new thread.
Another example of a multithreaded program that we are all familiar with is a word processor. While you are typing, multiple threads are used to display your document, asynchronously check the spelling and grammar of your document, generate a PDF version of the document.
Which is the best sorting algorithm? If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case. But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
We create a class that extends the java. This class overrides the run() method available in the Thread class. A thread begins its life inside run() method. We create an object of our new class and call start() method to start the execution of a thread. Start() invokes the run() method on the Thread object.
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.
28
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.
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
