Sorting

 Sorting Algorithms Bubble sort Insertion sort Selection sort Quicksort Merge sort Heap sort Introsort Counting sort Problems Problems solvable using 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 , $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)$ 