Advantages and Disadvantages of Quicksort over Merge sort
Theoretically, both quick sort and merger sort take O(nlogn) time and hence time taken to sort the elements remains same.
However, quick sort is superior than merge sort in terms of space.
Quick sort is in-place sorting algorithm where as merge sort is not in-place. In-place sorting means, it does not use additional storage space to perform sorting. In merge sort, to merge the sorted arrays it requires a temporary array and hence it is not in-place.
However time efficiency of the quick sort depends on the choice of the pivot element. Normally the middle or median element is chosen.
The other vulnerability with Quicksort is the use of a pivot. A poorly picked pivot can lead to bad runtimes (worst case being O(n^2)). For sufficiently random datasets, Quicksort works. The worst case is when your data is all the same (eg. All 1s). I imagine it's nearly as bad if your dataset is not very diverse as ell (eg. All 1s and 2s) as it will lead to very unbalanced partitions.
QuickSort is better than other sorting algorithms with same asymptotic complexity O(nlogn) (merge sort, heap sort). Even though quicksort has O(n^2) in worst case, it can be easily avoided with high probability by choosing the right pivot.
1. Its cache performance is higher than other sorting algorithms. This is because of its in-place characteristic.
2. If Quick sort is implemented well, it will be around 2-3 times faster than merge sort and heap sort. This is mainly because that the operations in the innermost loop are simpler. ( I read this from Algorithm Design Manual Book).
3. No extra memory.
Note : In Java, Arrays.sort() uses Quick Sort for sorting primitives and Merge Sort for sorting Arrays of Objects. This is because, merge sort is stable, so it won't reorder elements that are equal.
However, quick sort is superior than merge sort in terms of space.
Quick sort is in-place sorting algorithm where as merge sort is not in-place. In-place sorting means, it does not use additional storage space to perform sorting. In merge sort, to merge the sorted arrays it requires a temporary array and hence it is not in-place.
However time efficiency of the quick sort depends on the choice of the pivot element. Normally the middle or median element is chosen.
The other vulnerability with Quicksort is the use of a pivot. A poorly picked pivot can lead to bad runtimes (worst case being O(n^2)). For sufficiently random datasets, Quicksort works. The worst case is when your data is all the same (eg. All 1s). I imagine it's nearly as bad if your dataset is not very diverse as ell (eg. All 1s and 2s) as it will lead to very unbalanced partitions.
QuickSort is better than other sorting algorithms with same asymptotic complexity O(nlogn) (merge sort, heap sort). Even though quicksort has O(n^2) in worst case, it can be easily avoided with high probability by choosing the right pivot.
1. Its cache performance is higher than other sorting algorithms. This is because of its in-place characteristic.
2. If Quick sort is implemented well, it will be around 2-3 times faster than merge sort and heap sort. This is mainly because that the operations in the innermost loop are simpler. ( I read this from Algorithm Design Manual Book).
3. No extra memory.
Note : In Java, Arrays.sort() uses Quick Sort for sorting primitives and Merge Sort for sorting Arrays of Objects. This is because, merge sort is stable, so it won't reorder elements that are equal.
Subscribe to:
Post Comments
(
Atom
)
Can you Ensure all the information is correct??
ReplyDelete