Sorting and Efficiency (Week 11)

I feel the phrase "Worst case runtime" really confuses people. I like to think the "runtimes" (c, n, n^2, n!, etc) are more like worst case "rates of change". Because that's what they really are. How the running time on the algorithm CHANGES as the input grows. Because from what I've seen, a lot of people try to assign a value to this "runtime", for example, seconds. But unless a very deep analysis is done, it is difficult to put a real seconds value on some code, without actually testing it.

We talked about some sorting algorithms such as quick sort, merge sort, and the n^2 sorts. The one I liked the most was merge sort (aside from bogosort, of course). Mergesort is a nlogn sorting algorithm in its best, average, and worst case. It works by:
1) Recursively splitting up the list to be sorted (logn runtime)
2) When the list has been broken up into sublists each of size 1, the "merge" step kicks in.
The merge step consists of combining two lists into 1 larger sorted list. It does this in linear (n) run time by progressively checking the first index of the lists, comparing them, and appending the larger (or smaller) item into the larger list.
3) Step 2 is done recursively as the lists are rebuilt from their splitting size of 1 (from step 1), till finally two lists which are each half the size of the original list, are merged together into a fully sorted list.

The most impressive sort though, was timsort, which is the built in python list sort.
Timsort is roughly a combination of mergesort and insertion sort. It is also intelligent and is able to recognize partially sorted chunks of data, so that it does not have to waste time running the sort on the data.
Why insertion sort? Insertion sort is used because it has very good runtime on small lists (around 5~10 items). Because of the small size of the lists, there is a high probability that insertion sort will run at its best case runtime of (n). Therefore, what timsort roughly does is, split the list till it is smaller than a certain threshold, insertion sort the small lists, and then merge the larger lists. Also, because it is able to recognize sorted chunks, timsort is said to have "supernatural" best case run time of (n) steps. This takes place when the list is already pre-sorted in ascending or descending order.