Sorting and Efficiency

Week 11: Sorting and Efficiency

The last topic of CSC 148 is sorting and efficiency. My first exploration of this topic began in CSC 108, where the bubble, insertion, and selection sorting methods were introduced, and their run times were analyzed. Now we have turned to this topic again with more information. More sorting methods (quick and merge mainly) were introduced, their run times were analyzed, and we began using big O notation to describe efficiency.

To begin with sorting, here is a little summary. For quick sort, a pivot is chosen, then all values less than the pivot go to the left, all values greater than the pivot go to the right, and the pivot is in its proper position. After, quick sort is recursively called on each side of the pivot; the process continues until the list is sorted. For merge sort, the list is first divided in half. Merge sort is then recursively called to sort each half, and then the sorted halves are “merged” together.

Something I have noticed about these sorts is that they are generally much more efficient than bubble, selection and insertion sort. For example, all of the 108 sorts have a worst case run time of O(n²), while merge and quick sort's run times are generally O(nlgn). I wondered why this was, and then it occurred to me. The 108 sorts are iterative over multiple rounds. The number of comparisons in one round increases linearly with the size of the list, giving O(n). In addition, the number of rounds is simply the length of the list or sometimes the length of the list minus one. The number of rounds also increases linearly with the size of the list, giving O(n). This leads to the total number of comparisons/exchanges to be quadratic by the famous formula for the summation of every number from 1 to n. Merge sort, however, takes more recursive and binary approach. By dividing the list in half each round (a binary strategy), the number of recursive calls required only increases by one every time the list size doubles, greatly reducing the run time as opposed to a four fold increase for the 108 sorts. This is where the lgn comes from in merge's run time. So where does the additional n come from? In each recursive round of merge sort, all of the elements in the list are being compared. So the number of comparisons increases linearly with the size of the list, giving O(n). Therefore, the total number of comparisons is the number of comparisons in each round times the number of rounds. The number of comparisons in each round is n; the total number of comparisons is lgn, so the run time of merge sort is O(nlgn). The run time for quick sort offers a similar explanation to merge sort, but only if the pivot chosen lies in the middle of the list. When the pivot is in a middle position, the list is roughly divided in half, with a binary strategy like merge sort. However, when the pivot is too much to the left or too much to the right (in the worst case), quick sort starts to resemble a combination of insertion and bubble sort. The run time complexity here is O(n²), which is the same as both insertion and bubble sort in the worst case. So back to the first sentence of this paragraph, these new sorts are generally more efficient than the 108 sorts because by taking a binary approach, the number of rounds of comparisons is greatly reduced.

Of the things we learned in this class, the one I had the least practice and felt most uncomfortable with was sorting and efficiency (especially run time analysis). However, the examples in class, the past test question, and writing this slog helped me understand it better!