Menu
When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are equal to the pivot to the middle and then we recursively QuickSort those values on the left and those values on the right.
Merge sort generally performs fewer comparisons than quicksort both in the worst-case and on average. If performing a comparison is costly, merge sort will have the upper hand in terms of speed.
A simple solution would be to use efficient sorting algorithms like Merge Sort, Quicksort, Heapsort, etc., that can solve this problem in O(n. log(n)) time, but those will not take advantage of the fact that there are many duplicated values in the array. A better approach is to use a counting sort.
To use merge sort to remove duplicates, you would ignore elements that are repeated in the merging process. This reply answered the question recusively. take a look at the instructions for Mergesort.
See Quicksort on wikipedia:
Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.
Note that the very low memory requirement is a big plus as well.
Quick sort is typically faster than merge sort when the data is stored in memory. However, when the data set is huge and is stored on external devices such as a hard drive, merge sort is the clear winner in terms of speed. It minimizes the expensive reads of the external drive and also lends itself well to parallel computing.
For Merge sort worst case is O(n*log(n)), for Quick sort: O(n2). For other cases (avg, best) both have O(n*log(n)). However Quick sort is space constant where Merge sort depends on the structure you're sorting.
See this comparison.
You can also see it visually.
While quicksort is often a better choice than merge sort, there are definitely times when merge sort is thereotically a better choice. The most obvious time is when it's extremely important that your algorithm run faster than O(n^2). Quicksort is usually faster than this, but given the theoretical worst possible input, it could run in O(n^2), which is worse than the worst possible merge sort.
Quicksort is also more complicated than mergesort, especially if you want to write a really solid implementation, and so if you're aiming for simplicity and maintainability, merge sort becomes a promising alternative with very little performance loss.
I personally wanted to test the difference between Quick sort and merge sort myself and saw the running times for a sample of 1,000,000 elements.
Quick sort was able to do it in 156 milliseconds whereas Merge sort did the same in 247 milliseconds
The Quick sort data, however, was random and quick sort performs well if the data is random where as its not the case with merge sort i.e. merge sort performs the same, irrespective of whether data is sorted or not. But merge sort requires one full extra space and quick sort does not as its an in-place sort
I have written comprehensive working program for them will illustrative pictures too.
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