## The *QuickSort* Algorithm

QuickSort is a particularly effective and popular sorting algorithm. It
is a divide-and-conquer algorithm, working by splitting the data into two
parts and then sorting them recursively. Being recursive, it is often hard
to visualise what the algorithm is doing.

Here is the pseudocode algorithm for QuickSort:

quicksort(a[], p, r)
if r>p then
j=partition(a[], p, r)
quicksort(a[], p, j-1)
quicksort(a[], j+1, r)
partition(a[], p, r)
i=p
j=r+1
pivot=a[p]
do {
do i=i+1 while (a[i]<pivot)
do j=j-1 while (a[j]>pivot)
if (i<j) exchange(a[i], a[j])
}while (i<j)
exchange(a[p], a[j])
return j

The *Partition* method receives a list or sublist,
and places the first element in its correct position within the list.
It also ensures that all elements to the left of this are smaller, and
all to the right are larger.

The best and average cases of Quicksort take O(nlogn) time.

Go to QuickSort demonstration

Help on using the Applet

Back to main Page