Divide and Conquer Algorithms

The two sorting algorithms we've seen so far, selection sort and insertion sort, have worst-case running times of $\Theta(n^2)$. When the size of the input array is large, these algorithms can take a long time to run. In this tutorial and the next one, we'll see two other sorting algorithms, merge sort and quicksort, whose running times are better. In particular, merge sort runs in $\Theta(n \log n)$ time in all cases, and quicksort runs in $\Theta(n \log n)$ time in the best case and on average, though its worst-case running time is $\Theta(n^2).$Here's a table of these four sorting algorithms and their running times: