Sorting Recap

It felt like the treatment we did of sorting was pretty brief, but I found the subject fairly engaging. It also served as our first introduction into the analysis of algorithms. I'm going to use this blog to try to get my thoughts straight on the concept of sorting, as I consider it pretty likely that the subject is going to make a showing on the exam, considering it didn't appear on the second test.

Sorting is the process of ordering a list of elements in some sort of fashion. For example, we could try to sort a list of integers from smaller to largest(ascending order) or vice versa(descending order), or a list of words from shortest to longest, etc. We covered a few different approaches to sorting; namely mergesort, countsort, quicksort, and select sort.

Of the sorts I listed above, countsort came out on a top, if memory serves, with mergesort coming in second. I looked into why countsort did so well in the tests that professor Heap ran(it was briefly explained in class, but I didn't really catch the reason why) and it turns out the answer is pretty interesting. Most of the sorts we covered, like mergesort, or quicksort are what are called comparison sorts. This is because they directly compare the items they are sorting. For example, quicksort works by partitioning the list into sublists by picking a pivot and recursively quicksort-ing each sublist. Mergesort, on the other hand, breaks its input down into a series of pairs, which it sorts. It then compares each set of pairs etc, until it has ordered the entirety of the input. Agorithms like countsort, or professor Heap's favourite Radix sort, appear to be what are called integer sorts. We didn't really cover this in class, so I'm kind of shaky on what exactly integer sorts do. I'm going to try to figure it out and make it the topic of my next blog entry.