# 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.

Last updated