Implementations: My Github
Quick view
| Name | Best ($\Omega$) | Average ($\Theta$) | Worst ($O$) | Worst(Space Complexity) |
|---|---|---|---|---|
| Selection Sort | $\Omega(n^2)$ | $\Theta(n^2)$ | $O(n^2)$ | $O(1)$ |
| Bubble Sort | $\Omega(n)$ | $\Theta(n^2)$ | $O(n^2)$ | $O(1)$ |
| Insertion Sort | $\Omega(n)$ | $\Theta(n^2)$ | $O(n^2)$ | $O(1)$ |
| Quick Sort | $\Omega(n\log{n})$ | $\Theta(n\log{n})$ | $O(n^2)$ | $O(\log{n})$ |
| Heap Sort | $\Omega(n\log{n})$ | $\Theta(n\log{n})$ | $O(n\log{n})$ | $O(1)$ |
| Merge Sort | $\Omega(n\log{n})$ | $\Theta(n\log{n})$ | $O(n\log{n})$ | $O(n)$ |
| Radix Sort | $\Omega(nk)$ | $\Theta(nk)$ | $O(nk)$ | $O(n+k)$ |
Break up a problem into sub-problems, solve each sub-problem independently, and combine solution to sub-problems to form solution to original problem.