> For the complete documentation index, see [llms.txt](https://wiki.hanzheteng.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.hanzheteng.com/algorithm/cs/sorting.md).

# Sorting

### Selection Sort

* О(n^2) comparisons, О(n) swaps
* naive implementation for sorting

### Insertion Sort

* О(n^2) comparisons and swaps
* O(1) auxiliary space
* can run online
* stable

### Merge Sort

* O(n log(n)) by divide and conquer
* O(n) auxiliary space
* stable; deterministic

### Quick Sort

* O(n log(n)) by divide and conquer; worst case O(n) though
* O(1) auxiliary space; one of exchange sorts (cf. bubble sort)
* unstable; randomized

### Introsort

* hybrid sorting algorithm
* derived from quicksort, heapsort, and insertion sort
* unstable

### Timsort

* hybrid sorting algorithm
* derived from merge sort and insertion sort
* stable

### Distribution Sort

* O(n+m) non-comparative sorting algorithms: radix sort, bucket sort, digital sort, pigeonhole sort
* it avoids comparison by creating and distributing elements into buckets according to their radix
* the lower bound for comparative sorting algorithm is O(n log(n)); in certain cases, non-comparative sorting can do better, e.g., O(n)

### Topological Sort

* for directed acyclic graph (DAG)
* output a linear ordering of its vertices 

### Tree Sort

* builds a binary search tree from the elements to be sorted, and then traverses the tree (in-order) so that the elements come out in sorted order.
* Its typical use is sorting elements online: after each insertion, the set of elements seen so far is available in sorted order.