Sorting

From Algorithmist
Jump to: navigation, search
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[edit]

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

Sorting Algorithms and Complexities[edit]

  • 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)