# 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, ${\displaystyle S'=Sort(S)}$ is defined as follows:

• for ${\displaystyle 0, ${\displaystyle 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 ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ - in place, ${\displaystyle O(1)}$ extra space. Insertion sort ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ - in place, ${\displaystyle O(1)}$ extra space. Selection sort ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ - in place, ${\displaystyle O(1)}$ extra space. Merge sort ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ - ${\displaystyle O(n)}$ extra space. Heap sort ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ - in place, ${\displaystyle O(1)}$ extra space. Quicksort ${\displaystyle O(n^{2})}$ - ${\displaystyle O(n\log n)}$ expected, and with high probability. ${\displaystyle O(1)}$ inplace. Introsort ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ - ${\displaystyle O(\log n)}$ extra space. Counting sort ${\displaystyle O(k+n)}$ ${\displaystyle O(k)}$ Timsort ${\displaystyle O(n)}$ Best case ${\displaystyle O(n\log n)}$ Worst Case ${\displaystyle O(n)}$