Sorting Algorithms

Last week, we compared various sorting algorithms in our lab. Our results showed that Tim sort was the most efficient sorting algorithm, while quick sort and merge sort were the next fastest followed by insertion sort, selection sort, and bubble sort. For the purpose of this blog post, I will explain the general ideas of selection, quick and merge sort in order to offer an explanation as to why these efficiencies turned out to be the way they are.

Selection sort works by finding the minimum element from position i to the end of the list and then swapping this value with the value at index i. It takes about n - i operations to complete this step. Also, we require that i goes from 0 to n in order to completely sort the list. So the total number of operations will be given by (n + n - 1 + . . . + 2 + 1) = n*(n + 1)/2, which gives us a worst-case time complexity of O(n^2). Unfortunately the best-case time complexity is exactly the same as the worst-case time complexity for selection sort, since we require checking all n - i indices to ensure we have found the minimum value in the list (that means the running time will depend on n^2 even for a list that is already sorted).

Quick sort works by choosing some pivot (simpler implementations simply choose the first index of the list as the pivot), then partitioning the list into two sections: one section is a list containing values less than the pivot value while the other holds values greater than or equal to the pivot value. We sort these two sub lists recursively and then join everything together to get a sorted list. We perform about n operations for each recursive call, and we require about log(n) recursive calls to partition the list until only one element remains. So the average performance is O(n log n). There are cases, however, where this performance is much worse. As an example, consider a perfectly sorted list. Quick sort will choose the first index as the pivot. Since no element is smaller than the first element, one of the sub lists will be empty and the partition essentially does nothing. In this case, we require n recursive calls in order to split the list until one element remains (which means the worst-case time complexity is O(n^2)). A similar case occurs when the list is perfectly unsorted.

Merge sort works by splitting the list in half, sorting each half (recursively) and merging the sorted halves together. This has a similar time complexity as quick sort, we require log(n) recursive calls and perform n operations for each call so we have O(n log n). Unlike quick sort, there are no cases where merge sort behaves poorly. It is essentially guaranteed to run a time complexity of O(n log n).

Our data showed that quick sort runs faster on average. However, on sorted and unsorted data merge sort performed significantly faster (as expected). I would still prefer quick sort over merge sort since the average run time is faster. Also, to address the issues with sorted and unsorted data, we were taught a quick sort variant in Wednesday's lecture which chooses a random pivot. This variant does not have the same disadvantages on sorted data that the original algorithm has. And even though the worst-case complexity is still O(n^2), this is very rare. In fact, the chance that the minimum pivot would be chosen each time is 1/n! and similarly for the maximum pivot. So comparing merge sort and quick sort solely based on their worst-case time complexities is a meaningless comparison in this case. Therefore I claim that quick sort is generally faster than merge sort. Don't take my word for it though, this is simply my opinion based on what we have learned so far. I have noticed varying opinions on several forums about this topic. I am also aware that Tim sort is a hybrid sorting algorithm which uses merge sort. One would question why merge sort was chosen for this algorithm, so perhaps my opinion on this topic will change over time as I gain more knowledge.

Thanks for reading, let me know what you think about quick sort and merge sort in the comments.