Time and Space Complexities of Popular Sorting Algorithms

Sort	Worst Case TC	Avg Case TC	Best Case TC	Space Complexity	Is Stable
Bubble Sort	$O(N^2)$	$\Theta(N)$	$\Omega(N)$	$O(1)$	Yes
Selection Sort	$O(N^2)$	$\Theta(N^2)$	$\Omega(N^2)$	$O(1)$	No¹
Insertion Sort	$O(N^2)$	$\Theta(N^2)$	$\Omega(N)$	$O(1)$	Yes
Merge Sort	$O(N logN)$	$\Theta(N logN)$	$\Omega(N logN)$	$O(N)$	Yes
Quick Sort	$O(N^2)$	$\Theta(N logN)$	$\Omega(N logN)$	$O(N), O(logN)$	No
Heap Sort	$O(N logN)$	$\Theta(N logN)$	$\Omega(N logN)$	$O(1)$	No¹
Counting Sort	$O(N + R)$	$\Theta(N + R)$	$\Omega(N + R)$	$O(R)$	Yes

The default implementation is not stable, however it can be made stable using some special technique.
↩

Published 27 Jun 2021

CS Posts on Twitter