O(n lg n) - already-sorted data |
O(n log n) - already-sorted data |
Many common sort algorithms are used in computer science. They are often classified by:
Some sorting algorithms follow:
Name | Worst case complexity | Average case complexity | Best case complexity | Average case memory usage | Stable? |
---|---|---|---|---|---|
Bubble sort | O(n2) | O(n2) | O(n) - already-sorted data | works in-place | Yes |
Straight insertion sort | O(n2) | O(n2) | O(n) - already-sorted data | works in-place | Yes |
[Bucket sort]? | . | . | . | . | . |
[Counting sort]? | O(n) | . | . | Varies with data | N/A |
Heapsort | O(n log n) | O(n log n) | O(n log n) | works in-place | no |
Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) extra space | Yes |
Quicksort | O(n2) - already sorted data | O(n log n) | O(n log n) | works in-place, needs O(log n) auxiliary storage | No |
binary tree sort | O(n2) -- already sorted data | O(n log n) | O(n log n) | O(n), typically several pointers per input item | Yes |
Pigeonhole sort | O(n) | . | . | . | . |
Radix sort (k = keyspace size) |
O(n log k) | O(n log k) | O(n log k) | O(n) extra space | Yes |
[Shell sort]? (decreasing gap insertion sort) |
O(n1.5) | O(n1.25) | O(n log n) - already-sorted data | works in-place | No |
D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching.
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm has analyses of many of these algorithms.
Ricardo Baeza-Yates has many sorting algorithms on the Web at http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html