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