1

A test asked me to implement a sorting algorithm that sorts an array that when the size is N > 1000 by Merge sort, otherwise by Quick sort with the pivot is chosen randomly. Then suppose the keys to compare consists of randomly distributed integers on [1, M]. How M should be for the above algorithm to run best?

I let Quick Sort handles the recursive call of Merge Sort if the size is <=1000. In my opinion, because of random keys, random pivots and Hoare's partition scheme isn't slowed down by repeated elements if M is much smaller than N, Quick sort will run at its best, and Merge sort runs the same for a specific array size regardless of keys distribution, so what is M used for here?

Daanturo
  • 124
  • 2
  • 7
  • M = 1 would be "best", all elements have the same value, which helps with both Hoare based quick sort and merge sort. Seems like there should be more to the question about M. If doing an integer sort, radix sort would be much better than hybrid quick / merge sort. – rcgldr Jan 12 '20 at 10:15

1 Answers1

0

Quicksort must be implemented carefully to avoid pathological cases. Choosing the pivot at random is a good way to avoid quadratic time complexity on sorted arrays, but it is not sufficient for arrays with many duplicate elements.

If M is much smaller than N, you will have lots of duplicates. The original algorithm does not handle duplicates efficiently and this will cause quicksort performance to degrade significantly because Hoare's original algorithm only removes one element per recursion level on arrays with all identical elements.

See this question for a study of an actual implementation, its behavior on arrays with randomly distributed data in a small range and how to fix the quicksort implementation to avoid performance degradation: Benchmarking quicksort and mergesort yields that mergesort is faster

chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • The OP mentions he's using Hoare partition scheme, where the performance improves as the number of duplicates increase (despite needless swapping of elements equal to pivot). – rcgldr Jan 12 '20 at 10:13