This algorithm is often the best choice for sorting, because it’s remarkably efficient on average. It is a **divide and conquer algorithm.**

**Divide**: We partition the array in two subarrays.
**Conquer**: We sort the two subarrays by making recursive calls to the algorithm.

Example gif from wikipedia

Quicksort example from wikipedia

Pseudocode (from wikipedia)

quicksort(A, i, k):
if i < k:
p := partition(A, i, k)
quicksort(A, i, p - 1)
quicksort(A, p + 1, k)
// left is the index of the leftmost element of the subarray
// right is the index of the rightmost element of the subarray (inclusive)
// number of elements in subarray = right-left+1
partition(array, left, right)
pivotIndex := choose-pivot(array, left, right)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right]
storeIndex := left
for i from left to right - 1
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex
let arr be an unsorted array of integers
quicksort(arr,0,arr.length-1)

#### Implementations

C (Apple LLVM version 5.1 (clang-503.0.40), compiled with gcc -ansi)

#include <stdio.h>
void quicksort(int array[],int left, int right)
{
if(left < right)
{
int q = partition(array,left,right);
quicksort(array,left,q-1);
quicksort(array,q+1,right);
}
}
int partition(int array[],int left, int right)
{
int x = array[right];
int i = left - 1;
for(int j=left; j<right; j++)
{
if(array[j] <= x)
{
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[++i];
array[i] = array[right];
array[right] = temp;
return i;
}
int main()
{
int arr[] = {5,2,4,6,1,3};
int arrlength = sizeof(arr)/sizeof(arr[0]);
quicksort(arr,0,arrlength-1);
for(int i=0; i<arrlength; i++){
printf("%d ",arr[i]);
}
printf("\n");
}

Java 1.7

public class QuickSort{
public static void quickSort(int []array,int left, int right){
if(left < right){
int q = partition(array,left,right);
quickSort(array,left,q-1);
quickSort(array,q+1,right);
}
}
public static int partition(int array[],int left,int right){
int x = array[right];
int i = left - 1;
for(int j=left; j<right; j++){
if(array[j]<=x){
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[++i];
array[i] = array[right];
array[right] = temp;
return i;
}
public static void main(String []args){
int arr[] = {5,2,4,6,1,3};
QuickSort.quickSort(arr,0,arr.length-1);
for(int i : arr){
System.out.print(i+" ");
}
System.out.println();
}
}

Python 2.7.5

def quicksort(array,left,right):
if left < right:
q = partition(array,left,right)
quicksort(array,left,q-1)
quicksort(array,q+1,right)
def partition(array,left,right):
x = array[right]
i = left - 1
for j in range(left,right):
if array[j] <= x:
i = i + 1
temp = array[i]
array[i] = array[j]
array[j] = temp
temp = array[i+1]
array[i+1] = array[right]
array[right] = temp
return i + 1
arr = [5,2,4,6,1,3]
quicksort(arr,0,len(arr)-1)
print arr