Sorting is the rearrangement of numbers (or other orderable objects) in a list into their correct lexicographic order. Alphabetization is therefore a form of sorting. Because of the extreme importance of sorting in almost all computer algorithms and database applications, a great deal of effort has been expended in the creation and analysis of efficient sorting algorithms. A number of common sorting algorithms include heapsort, merge sort, quicksort, selection sort, and shellsort.
The following table summarizes the number of comparisons or elementary operations used by several comparison sorts, which determine order by comparing pairs of items,
on 
items. The bounds suppress constant factors
and lower-order terms. The base of the logarithm is immaterial in these big-O
bounds because changing the base multiplies the logarithm by a constant. Quicksort's
quadratic worst case can be avoided with suitable randomization or pivot safeguards,
while shellsort bounds depend on the chosen gap sequence.
| algorithm | best case | average case | worst case |
| heapsort |  |  |  |
| merge sort |  |  |  |
| quicksort |  |  |  |
| selection sort |  |  |  |
