Comment on page

# Sorting

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

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

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

- 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

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

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

- 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)

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

- 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 modified 2yr ago