Sorting and Efficiency

Sorting is the process of reorganizing a collection of items according to the desired criteria. This desired criteria is usually among ascending, or descending order. In computer science, there exist many types of sorting algorithms that get this job done. From my time in CSC108, the sorting algorithms that I have knowledge about are the bubble sort, insertion sort, and selection sort. However, recently I have learned about quick sort, merge sort, count sort, and python's default built-in sorting algorithm known as tim sort. One might think "why use one type of sorting over the other?" when all types of sorting algorithms can get the job done. Some notable reasons are that depending on the input to be sorted, some algorithms are more efficient than others. What do I mean by more efficient? If the sorting algorithm is given an input that is large in size, either ordered or non-ordered, performance will be quite different. For example, if a sorted list is given to both a program that utilises insertion sort and selection sort, insertion sort would perform better. This is because if the list is ordered, insertion sort just adds each element of the list to the sorted side without having to shift, or insert it into the right position. As a result, this takes at most n iterations. On the other hand, selection sort would still have to go through the whole unsorted side of the list each time to find either the biggest number or smaller number in the group. As a result, at least n^2 iterations are required for selection sort. Now imagine if the size of the input was 10,000. Insertion sort would go through 10,000 iterations while selection sort would go through 100,000, 000 iterations at the least. That would be a big difference in the amount of work the computer has to do. Thus, in this scenario selection sort is less efficient than insertion sort.

Computer scientists like to be able to analyze the run time complexity of algorithms. The notion that is used to represent the upper bound of the run time is known as the Big O. On a side note, the lower bound is known as the big omega and the tight bound (upper and lower bound) is known as big theta. I will be focusing on the Big O notion, but similar arguments can be made to the other two. As an example, the selection sort algorithm is based on a nested loop that depends on the size of n. Thus, selection sort will take at least n^2 iterations. The Big O notation in this case is O(n^2) which means that c*n^2 where c is a constant number is an upper bound for n^2 iterations. This means that the amount of iterations that selection sort takes is either equal to, or less than c*n^2 after a certain size of input. When talking about complexities of algorithms, only the effect at a large size of input is important to us because at a small size input the difference in efficiency is usually ignorable. So, how do we know what is an upper bound for each case? The following hierarchy sets the rules in place: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(n!) < O(n^n). The farther the Big O expression is in this inequality, the worst the performance is. Thus, computer scientists would prefer O(1), O(log n), O(n) over the other ones because at large size of input the difference is immense. 

I will now try to use this notion to describe the new sorting algorithms that I learned known as quick sort, merge sort, count sort, and tim sort. Quick sort is a sorting algorithm that depends on finding a pivot point and separating the elements that are larger than the pivot point to the right side and the elements that are smaller to the left side. This process is repeated n times and if the list is divided equally it will be defined by O(n log n). However, if the list is not divided equally each time, it will be defined by O(n^2) in the worst case. Thus, in the best case n log n is the upper bound for quick sort, but in the worst case c*n^2 is the upper bound for quick sort.

Merge sort is similar to quick sort in the aspect that it also divides the list into two sections and repeatedly does this until each list is a single element. Then, each list is compared with another and merged together into the right order. This process is repeated over and over again until the list is in the correct order. The number of times that merge sort divides the list is described by log n and because there are n elements, the process is repeated n times. Therefore, the Big O for merge sort is defined by

O(n log n). For example, if given the list [5,3,4,2,1], the list is divided into the lists [5,3] à [5] and [3] and [4,2,1]à[4] and [2,1]à[2] and [1]. [3] , [5] merges into [3,5], and [2] , [1] merges into [1,2] , and  [1,2] ,[4] merges into [1,2,4] , and [3,5] , [1,2,4] merges into [1,2,3,4,5].

Tim sort(known as the built-in sort function that python uses) is a sorting algorithm that uses a combination of insertion sort and merge sort to achieve its goal. Thus, the best case scenario is achieved when the list is ordered and insertion sort will only have to insert the items n times. The Big O notation would be defined as O(n) for the best case. However, in the worst case merge sort would be called n times and tim sort would take on the complexity for merge sort instead.  Therefore, tim sort has an order of n log n in the worst case.

In general, computer scientists only care about the efficiency of an algorithm when the size of the input is very large because the difference between small sized input results is usually dismissible. Imagine given a database with millions of entries and it is required to find one element in that database. Of course with our knowledge of the Big O, a searching and sorting algorithm for this problem is preferred to be on the left side of the hierarchy. By comparing the amount of resources used for a log n algorithm versus a n^3 algorithm, one can see the amount of time, resources, and money saved by efficiency. Therefore, sorting and efficiency is a very important topic for future years of computer science.