In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and lexicographical order.
Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists.
- Exchange Sorts
- Bubble sort: for each pair of indices, swap the items if out of order
- Cocktail shaker sort or bidirectional bubble sort, a bubble sort traversing the list alternately from front to back and back to front
- Comb sort
- Gnome sort
- Odd–even sort
- Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice
- Humorous or ineffective
- Bogosort
- Stooge sort
- Hybrid
- Flashsort
- Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
- Timsort: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.
- Insertion sorts
- Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
- Library sort
- Patience sorting
- Shell sort: an attempt to improve insertion sort
- Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list
- Cycle sort: in-place with theoretically optimal number of writes
- Merge sorts
- Merge sort: sort the first and second half of the list separately, then merge the sorted lists
- Strand sort
- Non-comparison sorts
- Bead sort
- Bucket sort
- Burstsort: build a compact, cache efficient burst trie and then traverse it to create sorted output
- Counting sort
- Pigeonhole sort
- Postman sort: variant of Bucket sort which takes advantage of hierarchical structure
- Radix sort: sorts strings letter by letter
- Selection sorts
- Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
- Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
- Smoothsort
- Other
- Bitonic sorter
- Pancake sorting
- Spaghetti sort
- Topological sort
- Unknown class
- Samplesort