From Algorithmist
Jump to navigation Jump to search
Bubble sort
Insertion sort
Selection sort
Merge sort
Heap sort
Counting sort
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[edit]

  • 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.
Counting sort
Timsort Best case Worst Case