Advanced Sorting Algorithms

In this lesson, we study more advanced sorting algorithms such as Quick Sort and Merge Sort. Both Algorithms are recursively implemented.

QuickSort Algorithm

As its name implies, quicksort is a fast divide-and-conquer algorithm. Its average running time is O(N log N). Its speed is mainly due to a very tight and highly optimized inner loop. It has quadratic worst-case performance, which can be made statistically unlikely to occur with a little effort. On the one hand, the quicksort algorithm is relatively simple to understand and prove correct because it relies on recursion. On the other hand, it is a tricky algorithm to implement because minute changes in the code can make significant differences in running time. We first describe the algorithm in broad terms. We then provide an analysis that shows its best-, worst-, and average-case running times. We use this analysis to make decisions about how to implement certain details in Java, such as the handling of duplicate items.

the quicksort algorithm

The basic algorithm Quicksort(S) consists of the following four steps.

1. If the number of elements in S is 0 or 1, then return

2. Pick any element v in S. It is called the pivot.

3. Partition S – {v} (the remaining elements in S) into two disjoint
goups:

4. Return the result of Quicksort(L) followed by v followed by
Quicksort(R).

Here is a figure that represents the quicksort algorithm.

Figure Courtesy of Weiss Data Structures Book

MergeSort Algorithm

Merge Sort is an algorithm that works as follows. Suppose we have two sorted arrays that we need to merge to form a single sorted array. If the sizes of the arrays are O(n), then we can merge them using a simple O(n) algorithm as follows. Suppose A and B are two sorted lists. We compare first element of A and first element of B. We merge the smaller of the two elements to a new list C. The process is shown below.

We continue this process until one array is completely processed. Then we merge the rest of the elements in the other array to C. One requirement of Merge Sort is that it needs an extra array to help the merging process.

Merge Sort is implemented recursively as follows. This is a divide and conquer algorithm. Divide initial array into equal halves and continue this process for all the sub-arrays until the array sizes become 1. Now by definition, an array of size 1 is sorted. Therefore we merge the size 1 arrays to form a sorted array of size 2. Then we merge two arrays of size 2 to form a sorted array of size 4 etc. We continue to merge these sorted arrays until the whole array is sorted.

Analysis

Both quick sort and Merge Sort algorithms are of order O(n log n). It is easy to understand why MergeSort is O(n logn). Here is a simple argument for that. In each step of the merge sort algorithm we divide the arrays into two equal halves. As we know, the depth of the tree formed is O(log n). Now each merging step requires O(n) steps and therefore the mergesort requires O(n logn) steps.

The average case analysis of Quick Sort is difficult and beyond the scope of this course. However, quick sort has shown to be the best algorithm that performs for a random set of data. It is easy to show that if the list is already sorted, then the quick sort performs bad typically requiring O(n²) steps. For over 40 years, quicksort has become the sorting algorithm of choice for many. None of the other algorithms seem to perform better than the quicksort on average.