Week 10/11: Sorting and Efficiency

To date, I had only been familiar with three types of sorting: bubble sort, selection sort, and insertion sort, which all had performance n^2.  That is to say ignoring the speed of the computer on which the program was being run, all these sorting functions would perform worse than a function with performance n.  Another way to think of it is if you doubled the size of the list that needed to be sorted, the time needed to sort the list would quadruple (in the worst case). 

This week, I learned of two other types of sorting: quicksort and merge sort.  Both are big-O of n log n, which is much better than the previously known sorting functions, which were all big-O of n^2.  For especially large lists, quicksort and merge sort would then run noticeably faster.  This can largely be attributed to their recursive structure.  While all our past sorting methods would involving passing over sections of the lists numerous times, quicksort and merge sort reduce that number by partitioning the list and reducing the number of items that we need to work with at a single time.  For instance, merge sort works by splitting the list in half each time, merge sorting each half, and then merging the sort halves.  We split the list log n times and make n comparisons each time (we compare each card in the set to every other card), giving us the n log n performance that we need.

In a world where data analysis involves working with lists unfathomably large, the performance of the sorting method we choose can then save us a significant amount of time. For instance, if I were using my code for scientific computation - say decoding the human genome - then there would be a huge difference between n log n run time and n^2 run time.  How large?  Depending on the volume  I was working with, this could in fact be a matter of days. 

Though today's post focused on quicksort and merge sort, it's worth pointing out that there are other sorting methods as well.  A notable example is timsort, pythons built-in sorting method which works differently depending on the list that has been passed.