Sorting Algorithms

Sorting algorithms

Sorting appears everywhere: a student management system orders records by student ID, an online store lists similar products from cheapest to most expensive, and a game ranks players from highest to lowest score.

Mainstream sorting algorithms fall into three broad complexity groups:

1. $O(n^2)$: bubble sort, selection sort, insertion sort.
2. $O(n\log n)$: merge sort, quicksort in its average case, heap sort.
3. Linear time under suitable range, distribution, and digit assumptions: counting sort, bucket sort, radix sort.

Many other algorithms are variations on traditional methods or unusual inventions, such as cocktail sort, bogosort, and sleep sort.

Sleep sort starts a thread for each value and sleeps for that many milliseconds. Threads with shorter sleeps should wake first. Although amusing, it has no practical value as a sorting method: large thread counts consume resources, close values need not be emitted in order, and a very large value could sleep for over a month.

Stability

Sorting algorithms can also be classified by stability:

• Stable sorting preserves the original relative order of equal-valued items.
• Unstable sorting may change that order.