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(n^{2}) |
O(n^{2}) |
O(n^{2}) |
O(1) |

Insertion Sort | O(n^{2}) |
O(n^{2}) |
O(n) | O(1) |

Bubble Sort | O(n^{2}) |
O(n^{2}) |
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(n^{2}) |
O(n log n) | O(n log n) | O(n) |