#Algorithms Quicksort VS Mergesort? Which is a faster sorting algorithm

Question

I did Google and found out that Quicksort is better then Mergesort, but my question is which is faster among both?

Comments

Quick sort is faster in some cases, but not all cases.

In case of performence, we have to check if it is best, average or worst case performence

---

thanks.

---

when we have large data set then which one to use and why ?

---

Quick sort and Merge sort both can handle large data set. As both uses divide and conquer rule.

Answer 1

Quicksort gives worst-case performance (i.e. O($n^2$) ) when the array is already sorted or almost sorted.In best case and average case quicksort takes O(nlogn) time . 

Time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves.

So based on cases in which you use these sorting algorithm each has its own benefit.

But when comparing the worst case performance of both algorithm merge sort is better .

Comments

thank you.

Answer 2

If the input contains random elements (i.e, not sorted, nearly sorted or same elements) then quicksort gives better performance than merge sort as though they have same best case time complexity Θ(n.logn) but quicksort runs faster by the constant factor which we ignore during asymptotic analysis.

Merge sort needs to copy the elements to another array which take extra time.

For more explanation, you may refer to this video