Foundations‎ > ‎Algorithms‎ > ‎

### Sorting

Sorting is the most fundamental problem in computer science. The followings are the most prominent sorting algorithms.

 Name Type Time Complexity Best Running Time Memory Stable* Notes Heapsort Comparison O(n log n) O(n log n) O(1) No Merge sort Comparison O(n log n) O(n log n) O(n) Yes Quicksort Comparison O(n2) O(n log n) O(log n) No When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. Insertion sort Comparison O(n2) O(n) O(1) Yes Bubble sort Comparison O(n2) O(n) O(1) Yes Counting sort Non-comparison O(n) O(n) O(n) Yes Assumes the input numbers are in the set {1,2...,k}. Linear time is achieved if k = O(n) Radix sort Non-comparison O(n) O(n) O(n) Yes Assumes the input numbers are in the set {1,2...,k} and and each number has d digits. Linear time is achieved if both d and k are O(n) Bucket sort Non-comparison O(n2) O(n) O(n) Yes Requires knowledge of the probabilistic distribution of the input External sort

*A sorting algorithm is not stable if the duplicate elements' order is changed during the sort