Week 12: Sorting and Efficiency

Despite how fast modern computer seem to accomplish our everyday tasks, there are still physical limits on the rate at which they can process information. It takes a real, non-negligible amount of time for a computer to read and execute a line of code. When performing a task on an input of a given size, some algorithms can be very efficient for small sized inputs, and hopelessly slow for larger inputs. This efficiency can often be modelled mathematically, as we will see.


When modelling the speed, or runtime, of a computer program, it is important to always take the worst case scenario. This means that it is the most useful if size is not considered the only factor, but other qualities of the state of the input as well. For example, if a sorting algorithm takes a list of 100 elements, it is not immediately clear how long it will take to process, since nothing is known about the state of the input, other than its size. It might already be sorted, in which case it would be absurd to say the algorithm works instantly for all inputs of that size. For this reason, it is important to take the worst case: the input of a certain size that will cause the algorithm to run for the longest time.


In class, we learned a variety of sorting algorithms, including insertion, selection, bubble and merge sort. Of these four, the first three have O(n^2) worst case time complexity, meaning for if the input is varied by n, then the time they take to sort the list varies quadratically. This means that for large inputs of n, they will take a long time to finish. Merge sort is different; it is O(n*log(n)). For large n, logn will be less than n, so this algorithm is faster than the previous three. However, this does not necessarily mean merge sort should always be used. For small inputs, it is unclear which of the four (and many more) algorithms is best.