Why Quick Sort is better than Merge Sort?

algorithms
better_algo
sorting

#1

Even though Quick Sort has a worst case of O(n^2) complexity which is slower than the worst case which is O(nlogn) for merge sort…why is quick sort is better than Merge sort in practice?


#2

Because merge sort has O(n) space complexity and Quick Sort has O(1) space complexity in all the cases.
Therefore in best and average case you can get O(nlogn) time complexity and O(1) space complexity using quick sort


#3

This is a very researched problem. (This is often asked in elementary level DS interviews too).
Please see here and here for more information.


#4

because quicksort does implay sorting which mergesort does not do


#5

You have to word you answer properly, because while you have let say array with n elements in memory, space complexity cannot be O(1)…


#6

What is implay sorting?


#7

@pruth:Under what circumstances it has O(1) space complexity?


#8

@Debanjan:Thnx very much.The provided links have been very useful and gave me a clear understanding