Sorting

In-place

Only constant amount of memory is allowed to be additonally used, which doesn't depent on data size $n$. In-situ.

Stable

Order is preserved (e.g. on equal values)

Algorithm Short description Worst Case Best Case Avg Case In-place Stable
Bubble Sort Simply swap elements $O(n^2)$ $O(n)$ $1/4 (n^2 - n)$ X X
Quick Sort Pick pivot, swap until $val[pivot-1] \Leftarrow val[pivot] \Leftarrow val[pivot+1]$; recursive apply for partitions $O(n^2)$ $O(n log n)$ $O(n log n)$ X
MergeSort Split list, until single elements; merge lists again in order $O(n log n)$ $O(n log n)$ $O(n log n)$ X X
BinaryTree Sort Insert in BinTree (balanced), in-order traversal (df: l-N-r) $O(n log n)$ $O(n)$ $O(n log n)$ (X)
Heap Sort Bin Max Heap; Exchange root with last element; Reduce heap size by one; Heapify; $O(n log n)$ $O(n log n)$ $O(n log n)$ X