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


  • hybrid sorting algorithm

  • derived from quicksort, heapsort, and insertion sort

  • unstable


  • 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