## 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^{2})
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.

##

##

##

##

##