• Similar to mergesort - divide-and-conquer recursive algorithm
• One of the fastest sorting algorithms
• Average running time O(NlogN)
• Worst-case running time O(N²)

1. Pick one element in the array, which will be the pivot.
2. Make one pass through the array, called a partition step, re-arranging the entries so that:
• the pivot is in its proper place.
• entries smaller than the pivot are to the left of the pivot.
• entries larger than the pivot are to its right.
3. Recursively apply quicksort to the part of the array that is to the left of the pivot,
   and to the right part of the array.

Here we don't have the merge step, at the end all the elements are in the proper order.

Here is the code, that implements the partitioning.
left points to the first element in the array currently processed, right points to the last element.

if( left + 10 <= right)
    {
	int i = left, j = right - 1;
	for ( ; ; )
	  {
	    while (a[++i] < pivot  ) {}   // move the left finger
	    while (pivot  < a[--j] ) {}	  // move the right finger

	    if (i < j) swap (a[i],a[j]);  // swap	
            else  break;		  // break if fingers have crossed
          }
       swap (a[I], a[right-1]);		  // restore the pivot
       quicksort ( a, left, i-1);	  // call quicksort for the left part
       quicksort (a, i+1, right);	  // call quicksort for the left part
     }
else  insertionsort (a, left, right);

If the elements are less than 10, quicksort is not very efficient.
Instead insertion sort is used at the last phase of sorting.

Compare the two versions:

A.
	while (a[++i] < pivot) {}
	while (pivot < a[--j]) {}

	if (i < j) swap (a[i], a[j]);
	else break;

B.

	while (a[i] < pivot) {i++;}
	while (pivot < a[j] ) {j--;}

	if (i < j) swap (a[i], a[j]);
	else break;

If we have an array of equal elements, the second code will never increment i or decrement j,
and will do infinite swaps. i and j will never cross.

Worst-case: O(N²)

Best-case O(NlogN) The best case is when the pivot is the median of the array,
and then the left and the right part will have same size.

Average-case - O(NlogN)

Analysis

The time to sort the file is equal to

• the time to sort the left partition with i elements, plus
• the time to sort the right partition with N-i-1 elements, plus
• the time to build the partitions

The pivot is the smallest element

Telescoping:

Add all equations:

The pivot is in the middle

Divide by N:

Telescoping:

Add all equations:

After crossing the equal terms:

Similar computations, resulting in T(N) = O(NlogN)

The average value of T(i) is 1/N times the sum of T(0) through T(N-1)

Multiply by N

To remove the summation, we rewrite the equation for N-1:

and subtract:

Prepare for telescoping. Rearrange terms, drop the insignificant c:

Divide by N(N+1):

Telescope:

Add the equations and cross equal terms:

The sum S (1/j), j =3 to N-1, is about LogN

Thus T(N) = O(NlogN)

Advantages:

• One of the fastest algorithms on average.
• Does not need additional memory (the sorting takes place in the array - this is called in-place processing). Compare with mergesort: mergesort needs additional memory for merging.

Disadvantages: The worst-case complexity is O(N²)

Commercial applications use Quicksort - generally it runs fast, no additional memory,
this compensates for the rare occasions when it runs with O(N²)

Never use in applications which require guaranteed response time:

• Life-critical (medical monitoring, life support in aircraft and space craft)
• Mission-critical (monitoring and control in industrial and research plants
  handling dangerous materials, control for aircraft, defense, etc)

Comparison with heapsort:

• both algorithms have O(NlogN) complexity
• quicksort runs faster, (does not support a heap tree)
• the speed of quick sort is not guaranteed

Comparison with mergesort:

• mergesort guarantees O(NlogN) time, however it requires additional memory with size N.
• quicksort does not require additional memory, however the speed is not quaranteed
• usually mergesort is not used for main memory sorting, only for external memory sorting.

So far, our best sorting algorithm has O(nlog n) performance: can we do any better?

In general, the answer is no.