Counting sort is so clever that it blew my mind, it doesn’t even use if clauses, this sorting algorithm doesn’t use comparisons. This algorithm can sort integer elements in the range 0 - k (k being exclusive)  where k it’s a known number. This is a great sorting algorithm when we have a large set of data in a range (0-k). It uses three arrays and has three for loops:

1. We fill a helper array of size k where every index in the helper array represents an element of the original array, and the value is the number of times that element is present in the original array. For example, if the number 0 appears 4 times in the original array, the index 0 of the helper array will contain a 4.
2. Using the information we have in the helper array, for every index of the helper array, we count how many elements are less or equal than that index, and we save that value in the corresponding index of the helper array. For example, if the number 0 appears 2 times, and the number 1 appears 3 times, in the helper array in the index 0 we are going to have the value 2, and in the index 1 we are going to have the value 5.
3. We fill up the result array by grabbing an element of the original array and placing it in it’s correct position on the result array, and every time we do that, we decrement the counter corresponding to that value in the helper array. 

Pseudocode

let arr be an array of integers of range 0-max
let res be an array of integers of the same length that arr
let max be the largest number of arr + 1
let tmp be an array of length max filled with zeros
for i=0 while i=0 k--
    res[tmp[arr[k]]-1] = arr[k]
    tmp[arr[k]] = tmp[arr[k]]-1

Implementations

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

#include <stdio.h>

int main()
{
	int arr[] = {5,2,4,6,1,3,0,5,0,4,2};
	int arrlength = sizeof(arr)/sizeof(arr[0]);
	int res[arrlength];
	int max = 7;
	int tmp[max];
	for(int h = 0; h<max; h++)
	{
		tmp[h] = 0;
	}
	for(int i=0; i<arrlength; i++)
    {
        tmp[arr[i]] = tmp[arr[i]]+1;
	}
   	for(int j=1; j<max; j++)
	{
        tmp[j] = tmp[j] + tmp[j-1];
	}
    for(int k=arrlength-1; k>=0; k--)
	{
		res[tmp[arr[k]]-1] = arr[k];
		tmp[arr[k]] = tmp[arr[k]]-1;
	}
	
	for(int l=0; l<arrlength; l++)
	{
		printf("%d ",res[l]);
	}
	printf("\n");
}

Java 1.7

public class CountingSort{

    public static void countingSort(int arr[], int res[], int max){
        int tmp[] = new int[max];

        for(int i=0; i<arr.length; i++){
            tmp[arr[i]] = tmp[arr[i]]+1;
        }
        for(int j=1; j<max; j++){
            tmp[j] = tmp[j] + tmp[j-1];
        }
        for(int k=arr.length-1; k>=0; k--){
            res[tmp[arr[k]]-1] = arr[k];
            tmp[arr[k]] = tmp[arr[k]]-1;
        }
    }

    public static void main(String []args){
        int array[] = {5,2,4,6,1,3,0,5,0,4,2};
        int result[] = new int[array.length];
        int max = 7;

        CountingSort.countingSort(array,result,max);

        for(int i : result){
            System.out.print(i+" ");
        }
        System.out.println();
    }

}

Python 2.7.5

def counting_sort(arr,res,max):
    tmp = [0]*max
    for i in range(0,len(arr)):
        tmp[arr[i]] = tmp[arr[i]]+1
    for j in range(1,max):
        tmp[j] = tmp[j] + tmp[j-1]
    for k in range(len(arr)-1,-1,-1):
	res[tmp[arr[k]]-1] = arr[k]
	tmp[arr[k]] = tmp[arr[k]]-1

array = [5,2,4,6,1,3,0,5,0,4,2]
result = [0]*len(array)

counting_sort(array,result,7)
print result

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