Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.

Mathematical analysis of quicksort shows that, on average, the algorithm takes O(nlogn) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare. [Wikipedia]

Here is implementation in C.

#include <stdio.h> void quicksort(int a[], int left, int right); int partition(int a[], int left, int right); int main(int argc, const char * argv[]) { int numbers[] = {5, 1, 0, 4, 2, 3}; int size = sizeof(numbers)/sizeof(numbers[0]); int i; printf("unsorted:"); for (i=0;i<size;i++) printf("%d ", numbers[i]); printf("\n"); quicksort(numbers, 0, size - 1); printf(" sorted:"); for (i=0;i<size;i++) printf("%d ", numbers[i]); printf("\n"); return 0; } void quicksort(int list[], int left, int right) { int pivotIndex; if ( left < right) { pivotIndex = partition(list, left, right); quicksort(list, left, pivotIndex - 1); quicksort(list, pivotIndex + 1, right); } } int partition(int list[], int left, int right) { int low, high, t, pivot; pivot = list[left]; low = left; high = right + 1; while (low < high) { do ++low; while (list[low] <= pivot && low < right); do --high; while (list[high] > pivot); if (low < high ) { t = list[low]; list[low] = list[high]; list[high] = t; } } t = list[left]; list[left] = list[high]; list[high] = t; return high; }