Counting Sort is a special case of indexed sort.

This algorithm can be applied only under very particular conditions but that, when such conditions are met, turns to be the fastest sort algorithm.
Range of different values should not be too large and values should be an numeric types.

1 ) Algorithm parses the original array determining its minimum and maximum value,
2 ) builds a temporary array of Long with one element for each possible value of the key.
3 ) Parses the original array again, this time counting the occurrences of each distinct value.
4 ) Evaluate where each value has to go in the sorted array.

#include  
#include  
#include  
#include  
#include  
using std::cout; 
using std::cin; 

int arr[] = {1,6,2,2,4}; 

void counting_sort(int *nums, int size) 
{ 
// search for the minimum and maximum values in the array 
int i, min = nums[0], max = min; 

for(i = 1; i < size; ++i) 
{ 
if (nums[i] < min) 
min = nums[i]; 
else if (nums[i] > max) 
max = nums[i]; 
} 

// create a counting array, counts, with a member for 
// each possible discrete value in the input. 
// initialize all counts to 0. 
int distinct_element_count = max - min + 1; 
int * counts = new int[distinct_element_count]; 

for(i=0; i{ 
counts[i] = 0; 
} 

// accumulate the counts - the result is that counts will hold 
// the offset into the sorted array for the value associated with that index 
for(i=0; i{ 
++counts[ nums[i] - min ]; 
} 

// store the elements in the array 
int j=0; 
for(i=min; i<=max; i++) 
{ 
for(int z=0; z{ 
nums[j++] = i; 
} 
} 

delete[] counts; 
} 

int main() 
{ 
counting_sort(arr, 5); 
}l