SPEAKER 1: Let's take a look at how you might have solved the sort problem. In this problem, we gave you three different programs that used three different sorting algorithms, selection sort, bubble sort, and merge sort. But we didn't tell you which was which. And your job was to figure it out by timing these programs on various different inputs. For example, we gave you this file random10000.txt with 10,000 numbers in random order, potentially sort. 

And one thing you might have tried is recognizing that both bubble sort and selection sort have a Big O running time of Big O of n squared. Whereas merge sort has a Big O running time of n log n. Then, for large random inputs, you should probably expect that merge sort is going to be significantly faster than both bubble sort and selection sort. So if we try these three programs on a file like random10000, but you might try it on some others, too, you would expect that merge sort should be the fastest. Let's try it out. 

Let's time ./sort1 on random10000.txt and see how long it takes to run ./sort1 on these 10,000 numbers. Here we see that it took 0.505 seconds for ./sort1, so about half a second. Let's try it again for ./sort2, and see how long it takes ./sort2 to do the same thing with the same file. OK. It took, in real terms, 0.038 seconds, significantly faster than the nearly half a second it took for ./sort1. 

But just for good measure, let's try ./sort3 as well. And compare ./sort3 against the other two sorting algorithms in terms of how long it takes. And it looks like this one also takes a little over half a second to be able to sort these 10,000 numbers. 

So based on that information, it seems pretty reasonable to conclude that ./sort2, the one which was the fastest on dealing with these random inputs, is probably merge sort. Between the other two, whether it's selection sort or bubble sort, we really don't know for sure just yet. But it's probably a pretty good guess that ./sort2 is going to be merge sort. And you could verify that for yourself by testing it on some other inputs as well. 

But now we need to figure out some way of distinguishing ./sort1 from ./sort3. Which one is bubble sort and which one is selection sort? And to do that, we can take advantage of what we know about each of their big omega running times. 

Bubble sort, we know, has a big omega of n running time. In an ideal case where all of the numbers are already sorted, bubble sort can sort the numbers very easily. It'll go through each of the numbers, one pair at a time, and realize that there are no swaps necessary, and then just declare that the numbers are already sorted in linear time without needing to make multiple passes through the array again and again. So we should expect that even though these two sorting algorithms had a very similar running time on a random file, if we gave them a big file that was already in sorted order, bubble sort should be much faster than selection sort. So let's try it out. 

The biggest file that's all in sorted order we have is sorted50000.txt, with 50,000 numbers, each of which is in sorted order. And let's try timing ./sort1 on that sorted50000.txt file, and see how long it takes in order to sort all of those numbers and print them out as well. It looks like it took a little over three seconds for ./sort1 to be able to sort and then print, all of those numbers, recognizing that it's going to take some time to print 50,000 numbers to the terminal as well. 

But let's compare that then to ./sort3 on that same input, sorted50000, and see how much time it takes for ./sort3 to do the same thing, sort these 50,000 numbers that are already in sorted order themselves. Whereas ./sort1 took about three seconds, it looks like this algorithm is taking closer to 7 seconds, more than double the amount of time required. And so based on that, and you could do some additional experiments, maybe testing these multiple times as well. 

But for sorted numbers, it seems that ./sort1 is outperforming ./sort3, whereas for numbers in random order, they're behaving pretty similarly. And that, then, is a pretty good sign that ./sort1 is probably bubble sort and ./sort3 is probably selection sort, given that we know that bubble sort performs better when the numbers are already in sorted order, whereas selection sort still needs to go through that entire array, looking for the smallest element every single time, making multiple passes through the array, even if the array is already in sorted order. 

And that then gives us our answer for which algorithm is in use by each of these programs. ./sort1 is using bubble sort. ./sort2 is using merge sort. And ./sort3 is using selection sort. My name is Brian. And this was sort.