The idea of "sorting" as a commonly-mentioned and ever-evolving topic in computer science has always struck me as interesting. What's interesting about it is, unlike some functions and abstract data types, we encounter it in daily life. We sort things all the time. But how would you explain to someone exactly how you came up with a sorted set of data? That's harder to do.
There are actually many ways to explain it because there are tons of methods. The reason there are so many algorithms is that the best run-time is always preferred. What's important to understand when comparing run-time analyses is that we do not really care about the run-time for smaller lists of items. We want to see how each algorithm can perform as the number of items approaches infinity. Because of this, when looking at the run-time equation for algorithms, what matters is the degree of the highest exponent. Constants are not much of a concern. Thus, we use "big-O" notation in front of functions.
One interesting thing about sorting that I didn't quite grasp at first is that some algorithms don't adhere to a worst-case or best-case condition and some do. For example, selection sort will always have n^2 run-time. This is because selection sort looks through the entire remaining list for the biggest number and then brings that number to the back of the unsorted part each time it passes. It looks like [unsorted | sorted] as it moves along. So, even if you have a list of, say, [1, 2, 3, 4, 5, 6], selection sort will run through the list and find 6 as biggest, then run through the remaining five items and find 5 as biggest, and so on. Even though the list is already sorted, and you'd think that would be beneficial, selection sort still takes the same amount of time to ensure a list is sorted as it would if it were unsorted.
Insertion sort, on the other hand, will have run-time that grows proportionally to the size of the list if the list is sorted. Insertion works by keeping a sorted sub-list at the beginning of the list, unlike selection sort. The list looks like this as it moves along: [sorted | unsorted] with the sorted section growing and the unsorted section dwindling with time. It takes each first new item that comes after the sorted list and places it where it belongs in the sub-list. When insertion sees [1, 2, 3, 4, 5, 6], then, it looks at 1, sees that it is in place, then it looks at 2 and sees that it is in place, then it looks at 3, and so on. So it just goes through checking each item. This O(n) run-time is the best-case scenario, while O(n^2) is its worst time, occurring when the list is unsorted.
Learning about sorting and efficiency also revealed to me why binary search trees are so useful. These trees have O(log(n)) run-time in the best-case scenario. This is better than constant or exponential run-time, and it occurs because the data is divided into two parts based on the criteria of whether it's larger or smaller than the root. At first, I did not really understand why BSTS have O(n) run-time in the worst case. It then became apparent to me that this run-time occurs with a unary tree, when there is only one main branch. This makes sense since the tree basically resembles a linear list.
