[algorithm] Quick Sort Vs Merge Sort

quicksort is named so for a reason ,

highlights : both are stable sorts,(simply an implementation nuisance ) , so lets just move on to complexities

its very confusing with just the big-oh notations being spilled and "abused" , both have average case complexity of 0(nlogn) ,

but merge sort is always 0(nlogn) , whereas quicksort for bad partitions, ie skewed partitions like 1 element-10 element (which can happen due to sorted or reverse sorted list ) can lead to a 0(n^2)..

.. and so we have randomized quicksort , where we pick the pivot randomly and avoid such skewed partitioning , thereby nullifying the whole n^2 scenario anyway even for moderately skewed partitioning like 3-4 , we have a nlog(7/4)n, ideally we want 1-1 partion , thus the whole 2 of O(nlog(2)n).

so it is O(nlogn) , almost always and unlike merge sort the constants hidden under the "big-oh" notation are better for quicksort than for mergesort ..and it doesnt use up extra space like merge sort.

but getting quicksort run perfectly requires tweaking ,rephrase , quicksort provides you opportunities to tweak ....