QuickSort

First, the sequence to be sorted a is partitioned into two parts, such that all elements of the first part are less than or equal to all elements of the second part (divide). Then the two parts are sorted separately by recursive application of the same procedure (conquer). combination of the two parts yields the sorted sequence (combine).

void quicksort (int* a, int left, int right)

{

// left is the left index, right is the right index

// of the region of the array that is to be sorted

int i=left, j=right, temp;

int pivot=a[(left+right)/2];

// stopping case

if(left>=right) return;

// partition

do

{

while (a[i]<pivot) i++;

while (a[j]>pivot) j--;

if (i<=j)

{

temp=a[i]; a[i]=a[j]; a[j]=temp;

i++; j--;

}

} while (i<=j);

// recursion

quicksort(a, left, j);

quicksort(a, i, right);

}