Efficiency and Sorting

    For the past few weeks, we have been ignoring recursion(Yay!) and focusing on something that really peaks my interest, sorting lists, and the efficiency of these functions and of many more beyond that. The types of sorting algorithms studied in detail include: Selection Sort, Bubble Sort, Quick Sort, Insertion Sort and Merge Sort. In addition, we learned briefly about the extremely efficient default sort on python, Timsort. Finally, the way efficieny was measured for these algorithms is by Big-Oh analysis. The rules of this type of analysis state that when declaring the efficiency of a function, you must first find the general equation of how many steps are run then simplify it to the highest power and that is your Big-Oh. Selection sort, Bubble sort, and Insertion sort are all methods we had learned in CSC 108, and all have the same Big-Oh of O(n^2). These are the 'simpler' sorting algorithms and use loops to sort through the entire list, which is why they have that efficiency. While their exact equations are not n^2 (they could be something like 5n^2 + n + 27), we round to the highest power because of the fact that at some point, the constants, and even the value of any powers lower than the highest in the equation would become meaningless at very high list sizes. Merge sort, Quick sort, and Timsort however, have a O(n log n). This is because they seem to divide the list up into smaller lists, and divide and sort those. While this sounds scary, it turns out it is much more efficient that the previous three sorting algorithms mentioned.  While O(n^2) might seem inefficient compared to these superior algorithms, it is still in the acceptable range of programs. Programs that run on O(n!), or even O(n^n), are the point where efficiency is compromised, and is deemed unacceptable.