Big O and Sort Algorithms

Big O notation is a somewhat complex idea for me to wrestle with, or it initially was at least, but after spending a decent amount of time learning about it in 165 I have come to a decent understanding of it by the time we began to discuss it.  Essentially Big O seeks to describe the worst a program's runtime can possibly be, given constant sums and factors of difference (essentially selecting the highest order term such that choosing a lesser order term, regardless of constant multiple, would still be faster than the program given a high enough set of inputs.

For me it was helpful to observe graphs of the different types of inputs and how big-O big-Omega and big-Theta functions would compare to them.  This seems like the simplest way to intuitively understand runtime analysis, in my opinion.

Sort Algorithms are numerous though there are a couple of categories that they typically fall into.  We have looked at Selection, Insertion, Bubble, Merge, and Quick Sort.

Selection seems only to be a good idea to use if you are certain it will only be run over extremely small lists of data, the algorithm runs extremely slowly by seeking out smallest items on each iteration and returning them to the front, but this obviously creates a problematic runtime as it must traverse the entire list one time per item in the list.  Not a recommended sort in most contexts

Insertion is somewhat similar to selection but iterates the opposite way, running through the sorted portion of the list to insert each subsequent item where it belongs within that sort, therefore only traversing the unsorted list once (one item each time) and only traversing the entire sorted list when the next selected item is larger than all existing sorted elements.  Intuitively this makes it actually run slightly slower on already sorted data, and it is not a large improvement over selection, having a similar general runtime.  Also not typically recommended.

Bubble sort is the worst sort algorithm.  Do not use.  Must traverse entire list comparing pairs of elements to move the largest to the back on every iteration.  Very unwieldy.  We have been told there are situations where it may help but none that I have yet seen.

Merge Sort is an efficient algorithm which splits the list and sorts sides separately.  It can generally be an effective algorithm to use.

Quick Sort seems the best of the default choices we have been presented with (aside from builtins) as it can repeatedly split and sort smaller lists, combining them back together into a whole in a very effective and time efficient matter.