|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.
Given a list S with N elements, is defined as follows:
- for , .
- 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||- in place, extra space.|
|Insertion sort||- in place, extra space.|
|Selection sort||- in place, extra space.|
|Merge sort||- extra space.|
|Heap sort||- in place, extra space.|
|Quicksort||- expected, and with high probability.||inplace.|
|Introsort||- extra space.|
|Timsort||Best case Worst Case|