Which is the fastest sorting algorithm? Bubble, merge, or quick sort?
@jessie_marcelo (146)
Philippines
December 18, 2006 7:23pm CST
Which is the fastest among the three sorting algorithms namely: bubble sort, merge sort, and quick sort? Why is it so?
Do you know other sorting algorithms? Please share them with me.
1 response
@thundercat (505)
• United States
19 Dec 06
This really depends on the state of the array to be sorted, if it is nearly sorted or not. Bubble sort out of the three is definitely not the fastest as in worst case it runs in O(n^2) if you are familiar with big O notation and asymptotic complexity. This is compared to merge and quick sort which go in expected time O(n log n), and in practice quick sort is the best for most types of data.
@WebGal (48)
• United States
19 Dec 06
I recommend taking a look at wikipedia's entry on sorting algorithms:
http://en.wikipedia.org/wiki/Sorting_algorithm
Of the three algorithms mentioned in the original question, merge sort and quicksort perform in O(n log n) for best and average cases, beating out bubblesort's uniformly O(n^2) behavior; between the two, only merge sort achieves O(n log n) for the worst case, while quicksort's worst case goes to O(n^2).
The wikipedia article lists a number of other algorithms. Smoothsort and 'Patience sorting' are interesting in that they are the only algorithms listed that achieve O(n) performance in the best case and O(n log n) in the worst.
