Sorting and Efficiency

    Ever since I took 165 last semester, I had been interested in the concept of efficiency, and to a lesser extent, sorting. The fact that different sorting algorithms have different efficiency levels according to the best case, the average case, or the worst case is intuitive, and a very exciting thing to think about. For example,  an algorithm such as selection sort has N^2 running time, with N being the length of the list. Even in the best case, selection sort needs to check every element of the list, hence the running time is still N. The difference between N running time and N^2 running time seems small at first, but for large numbers of N, the difference is very substantial and noticeable. This difference is easily noticed when comparing the speed of two algorithms. For example, a race was demonstrated in lecture that featured select sort and merge sort. For small lists with less then 100 elements, the time difference was miniscule, and the race was very close. However, for large unsorted lists, merge sort was clearly the better algorithm. Merge sort boasts a worst case running time of NlgN, clearly trumping the N^2 worst case of selection sort. Merge sort has a better running time in most cases because instead of looking through every element of the list, it eliminates redundancy by cleverly manipulating the list into halves, and recursively calling merge on the both the left side of the list, and the right side of the list. Sorting lists has been a fascinating topic to study, and the different methods to sort lists are all quite clever in their implementation, especially the recursive ones.