In the past two videos, we've seen that we can get radically different performance from different implementations of the same functionality. However, we've also seen that small differences don't matter that much. In this video, we'll calculate the complexities of a few real algorithms, to show that picking the right design -- the right algorithm -- before starting to implement code is important.

We will be looking at three different implementations of *sorting* functions. Sorting functions take an array, like this one,

and transform it into an array where the values in the array are in non-decreasing order. That's increasing order, with the possibility of duplicate values.

The three algorithms we'll look at are bubble sort, selection sort, and merge sort. All three algorithms sort arrays correctly. The question is -- is there a right choice if you need to implement one?

Our first algorithm is bubble sort. It gets its name from how it works.

Bubble sort walks through the array, swapping adjacent values if they are not in the correct order. This means that if the largest value is at the very beginning of the array, it will "bubble up" to the end of the array in just one iteration.

How does it do? We're using timing code very similar to the code you've seen in the past two videos. This program
runs several trials of increasing size.

In each trial, it creates an array with random values in it,

times the sort,

and checks to make sure the sort ran correctly.

Here are the results for bubble sort. What is the complexity of bubble sort?

From its structure, we would guess quadratic -- big-o of n squared. We perform up to one swap per iteration of the inner loop, and that inner loop is executed n squared times, where n is the size of the array being sorted.

And our data seems to bear that out. It takes about 4 times as much time to sort an array that is twice as large.

Here's our second sort. Unlike bubble sort, which does a sequence of swap operations, selection sort works by

looking for the smallest value remaining and then

performing a single swap to put it in the right place. How do you think this function will compare to bubble sort?

Selection sort uses a nested loop, like bubble sort. But it does assignment, rather than a swap inside. So it's probably still quadratic, but it feels like swap is more expensive than a simple assignment.

And sure enough, although selection sort is faster than bubble sort,

they grow at the same rate. It takes selection sort roughly four times as long to sort an array that's twice as big.

Of these two functions, which would you prefer? They have the same complexity, and they both look fairly simple to implement. It's probably a toss-up.

So here's our final sort. It's clearly a more complex function.

While it contains a loop, that loop isn't the major part of the work. This function is recursive. It calls itself twice -- once on each half of the array.  Merge sort works by sorting each half of the array separately and then
merging the two halves together. It does so by copying into a new array and then

copying over the original array.

But how does it perform? It certainly has more code ...

but it is far faster.

It doesn't take four times as long to sort an array that's twice as large. It takes just over twice as long. It turns out that this algorithm, if you were to analyze it fully, is big-o of n-log-n. That's slower than linear but faster than quadratic.

So which do you choose? merge sort is clearly the fastest on integers. But it's also the most difficult to write correctly.

Remember what we said earlier? Correctness is the most important factor. Clarity is also important. And then performance is next. If you're not in a performance critical application, then some programmers would choose to implement bubble sort or selection sort. However, in a performance critical setting, most programmers would choose a faster sort -- like merge sort -- or an even more specialized sort based on the kind of data being sorted and whether or not other performance issues, like disk accesses, are relevant. Complexity is important but is just one factor when picking the right design.