Bubble sort

$\Theta\left(N\right)$

$\Theta\left(N^2\right)$

$\Theta\left(N^2\right)$

$\Theta(1)$

Yes

Selection sort

$\Theta \left(N^2\right)$

$\Theta \left(N^2\right)$

$\Theta \left(N^2\right)$

$\Theta(1)$

No

Stable with $\Theta(N)$ extra memory.

Insertion sort

$\Theta\left(N\right)$

$\Theta\left(N^2\right)$

$\Theta\left(N^2\right)$

$\Theta(1)$

Yes

$\Theta(N)$ if almost sorted.

Heapsort

$\Theta(N \log N)$

$\Theta(N \log N)$

$\Theta(N \log N)$

$\Theta(1)$

No

Merge sort

$\Theta(N \log N)$

$\Theta(N \log N)$

$\Theta(N \log N)$

$\Theta(N)$

Yes

Good cache performance

Random Quicksort

$\Theta(N \log N)$

$\Theta(N \log N)$

$\Theta \left(N^2\right)$

$\Theta(\log N)$ for the stack frames, $\Theta(1)$ otherwise

No

Fastest sort