Sorting

Sorting is a fundamental algorithm in Computer Science. A sorting algorithm takes a list as the input, and returns a list in an order. It is often the first step in many algorithms, and thus setting the lower bound for complexity.

Definition

Given a list S with N elements, $S'=Sort(S)$ is defined as follows:

• for $0<i\leq N$, $S_{i}\leq S_{i+1}$.
• S' is a permutation of S.

Sorting Algorithms and Complexities

• n is the number of elements
• k is the number of distinct objects

Algorithm	Time Complexity	Space Complexity
Bubble sort	$O(n^{2})$	$O(n)$ - in place, $O(1)$ extra space.
Insertion sort	$O(n^{2})$	$O(n)$ - in place, $O(1)$ extra space.
Selection sort	$O(n^{2})$	$O(n)$ - in place, $O(1)$ extra space.
Merge sort	$O(n\log n)$	$O(n)$ - $O(n)$ extra space.
Heap sort	$O(n\log n)$	$O(n)$ - in place, $O(1)$ extra space.
Quicksort	$O(n^{2})$ - $O(n\log n)$ expected, and with high probability.	$O(1)$ inplace.
Introsort	$O(n\log n)$	$O(n)$ - $O(\log n)$ extra space.
Counting sort	$O(k+n)$	$O(k)$
Timsort	$O(n)$ Best case $O(n\log n)$ Worst Case	$O(n)$