# Counting Sortby Isai Damier, Android Engineer @ Google

```/***************************************************************************
* Author: Isai Damier
* Title: Countingsort
* Project: GeekViewpoint
* Package: algorithms
*
* Statement:
*   Given a disordered list of repeated integers, rearrange the integers
*   in natural order.
*
* Sample Input: {4,3,2,1,4,3,2,4,3,4}
*
* Sample Output: {1,2,2,3,3,3,4,4,4,4}
*
* Time Complexity of Solution:
*   Best Case O(n+k); Average Case O(n+k); Worst Case O(n+k),
*   where n is the size of the input array and k means the
*   values range from 0 to k.
*
* Approach:
*   Counting sort, like radix sort and bucket sort,
*   is an integer based algorithm (i.e. the values of the input
*   array are assumed to be integers). Hence counting sort is
*   among the fastest sorting algorithms around, in theory. The
*   particular distinction for counting sort is that it creates
*   a bucket for each value and keep a counter in each bucket.
*   Then each time a value is encountered in the input collection,
*   the appropriate counter is incremented. Because counting sort
*   creates a bucket for each value, an imposing restriction is
*   that the maximum value in the input array be known beforehand.
*
*   There is a great number of counting sort code on the Internet,
*   including on university websites, that erroneously claim to be
*   bucket sort. Bucket sort uses a hash function to distribute
*   values; counting sort, on the other hand, creates a counter for
*   each value -- hence the name.
*
* Implementation notes:
*
* 1] Since the values range from 0 to k, create k+1  buckets.
* 2] To fill the buckets, iterate through the input array and
*    each time a value appears, increment the counter in its
*    bucket.
* 3] Now fill the input array with the compressed data in the
*    buckets. Each bucket's key represents a value in the
*    array. So for each bucket, from smallest key to largest,
*    add the index of the bucket to the input array and
*    decrease the counter in said bucket by one; until the
*    counter is zero.
**************************************************************************/
public void countingsort(int[] input, int k) {
// create buckets
int counter[] = new int[k + 1];
// fill buckets
for (int i : input) {
counter[i]++;
}
// sort array
int ndx = 0;
for (int i = 0; i < counter.length; i++) {
while (0 < counter[i]) {
input[ndx++] = i;
counter[i]--;
}
}
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

/**
* Test of countingsort method, of class Sorting.
*/
@Test
public void testCountingsort() {
System.out.println(""countingsort"");
int[] input = {6, 4, 3, 2, 1, 4, 3, 6, 6, 2, 4, 3, 4};
int k = 6;
Sorting instance = new Sorting();
instance.countingsort(input, k);
for (int i = 1; i < input.length; i++) {
if (input[i - 1] > input[i]) {
fail(""countingsort method fails."");
}
}
}
}```