Many people probably will not think that tidying a room is intellectually challenging, but to me, it took a lot of thinking time when I was in high school. From folding and putting the pile of clothes from laundry away to filing the notes of every courses, many tasks involve some kind of sorting and I always want to know the best way to do it. It turns out that the same problem is encountered in computer science, and computer scientists have invented and characterized many different algorithms - so many that the problem for me now is to determine what criteria do I have for my room tidying problem so I can pick the most effici algorithm.
To start with, we will need some way to describe the algorithm, and in computer science it is done with a description of the complexity of the algorithm. The analysis can be done on resources (such as memory space and time), but it is not limited to those - instead we can work on, say, the number of arithmatic operation. After picking a certain criterion, we can study the behavior of the algorithm in different scenarios, and in a lot of times we wil study the asymptotic worse case scenario complexity. This is the case where we concern about what is the worst that can happen given a large enough input. This is useful since the situation resources usage is actually of high importance is in large-scale application and it is best to optimize in this setting.
And now we can talk about the basic algorithms. As discussed in the post on recursion, it is easier to talk about them recursively even though they can be done iteratively, and that is what we are going to go through. The algorithms are then divided into two groups - the linear recursion ones and the divide-and-conquer ones. All of them are really common and I will not cover the details of the algorithm.
Bubble sort, selection sort and insertion sort all belongs to the first group. Essentially they work by reducing the problem size by one in each recursion, and solving the linear recurrence relation will give that the complexity will scale like the square of the size of input in the worse case.
Merge sort and quick sort are the divide-and-conquer ones, which break down the original problem into two (can be more) sub-problems and combine the results. This kind of recursion is solved by the Master Theorem (or more generally the Akra-Bazzi method), and it turns out that, given the pivot in quick sort is chosen well (go search online for details), both merge sort and quick sort scales like product of the size of the input and its logarithm. And it has been proved that this is the best you can get from algorithms that is based on comparison.
Of course, nothing is perfect and the way asymptotic complexity characterizes algorithms has it own deficit. First it just says it scales like certain function, but the constant of proportionality is hidden. In fact the constant might be so large that it is better to use an algorithm of higher complexity if the input is not 'large' large. Also, implementing the algorithm requires extra care if some other non-performance related characteristics of the input has to be considered (such as stability). It should also be mentioned that a lot of inputs, like the untidiness of my room, is not usually the worse case and the actual average behavior can vary. (Unfortunately average case scenario is much harder to analyze.)
The morale of the story, I suppose, is that the problem in my room does not worth the time used on analyzing algorithms.
