For the purposes of this example, let’s consider the numbers 1 through 8 in the following unsorted order:
4 2 6 8 1 3 7 5
For our first algorithm, we’ll work our way from left to right and compare two numbers at a time. If they’re out of order we’ll swap them and move on. So in the first run, we swap 4 and 2, then 8 and 1, then 8 and 3, then 8 and 7, then 8 and 5. This is what we’re left with:
2 4 6 1 3 7 5 8
Not quite fully sorted, but at least the number 8 bubbled up to the end where it belongs. Let’s do it a few more times:
2 4 1 3 6 5 7 8
2 1 3 4 5 6 7 8
1 2 3 4 5 6 7 8
For our second algorithm, we’ll again work our way from left to right and keep track of the smallest number we encounter on each iteration through the numbers. On the first iteration of the loop, we find that the number 1 is the smallest. We then swap 1 with the number at the front of the list. Alternatively, we could have shifted all the numbers at the front of the list to the right, but that is way more time consuming. Using the swap instead, our numbers now look like this:
1 2 6 8 4 3 7 5
On the second iteration, we find that the smallest number (2) is already in the correct place. Successive iterations transform the list as follows:
1 2 3 8 4 6 7 5
1 2 3 4 8 6 7 5
1 2 3 4 5 6 7 8
linear search | binary search | bubble sort | selection sort | insertion sort | merge sort | |
O | n | log n | n2 | n2 | n2 | |
Ω | 1 | 1 | n | n2 | n | |
Θ | n2 |
In pseudocode, merge sort is fairly easy to express:
On input of n elements:
If n < 2
Return.
Else:
Sort left half of elements.
Sort right half of elements.
Merge sorted halves.
When n is less than 2, there’s nothing to do. A list of one element is already sorted. This we’ll call the base case.
To calculate the runtime of merge sort, we can use the following notation:
T(n) = 0, if n < 2
T(n) = T(n/2) + T(n/2) + n, if n > 1
Consider the case where n = 16:
T(16) = 2 * T(8) + 16
T(8) = 2 * T(4) + 8
T(4) = 2 * T(2) + 4
T(2) = 2 * T(1) + 2
T(1) = 0
Since the base case takes 0 steps, we can now substitute 0 in for T(1)
and calculate T(2)
:
T(2) = 2 * 0 + 2
= 2
Now we can substitute 2 in for T(2)
and so on until we get:
T(16) = 2 * 24 + 16
T(8) = 2 * 8 + 8
T(4) = 2 * 2 + 4
T(2) = 2 * 0 + 2
T(1) = 1
T(16)
is 64. This number is actually n log n. Dividing the list successively accounts for log n, but the addition n factor comes from the merge step. Our runtime chart now looks like this:linear search | binary search | bubble sort | selection sort | insertion sort | merge sort | |
O | n | log n | n2 | n2 | n2 | n logn |
Ω | 1 | 1 | n | n2 | n | |
Θ | n2 |