I recently did some searching and had a very hard time finding a simple yet comprehensive listing of the running times for various sorting algorithms. This surprised me, so I decided to make the Internet a little better by writing this post.
This is an ongoing post, and will be updated with more algorithms as time goes on. It is not limited to just array sorting; it could be a graph search problem, a regression, or any other algorithm as long as it's pretty well-known. I welcome your additions in the comments section.
| Algorithm | Worst-Case | Average-Case | Best-Case | Space Growth |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) |
| Insertion Sort | O(n2) | O(n2) | O(n) | O(1) |
| Bubble Sort | O(n2) | O(n2) | O(n) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Quicksort | O(n2) | O(n log n) | O(n log n) | O(n) |