Counting sort in an \(O\left(n+m\right)\) sorting algorithm (instead of the usual \(O\left(n\log n\right)\)) for integer values, where \(n\) is the number of elements to sort and \(m\) is the width of the data type (e.g., \(2^{8}\) for byte). Its premise is quite simple. Given enough memory, it creates an array the width of the data type, iterates over the collection to be sorted, counts the number of recurring values in the array, and finally produces the sorted collection by iterating over the counts. This is trivial for byte through short data types. From there, it depends on system memory, and requires the use of multidimensional arrays as the number of potential values (i.e., negative through positive) exceeds the maximum collection index value of \(2^{31}-1\). For instance, int will require a int[2][Integer.MAX_VALUE] array equaling \(2*2^{31}*sizeof(int)=2^{32}*4=2^{34}=16\)GBs of memory just for the counting array – more is required for the actual array being sorted.
In this example, counting sort algorithms for byte, char, and short are provided.
/**
* Counting sort examples
* @author Ray Hylock
*/
public class CountingSort {
// size of each type
private static final int NUM_BYTE_VALUES = 1 << 8; // 256
private static final int NUM_CHAR_VALUES = 1 << 16; // 65,536
private static final int NUM_SHORT_VALUES = 1 << 16; // 65,536
// temporary arrays for sorting - single instantiation to save space
private final byte[] BYTE_SORT = new byte[NUM_BYTE_VALUES];
private final char[] CHAR_SORT = new char[NUM_CHAR_VALUES];
private final short[] SHORT_SORT = new short[NUM_SHORT_VALUES];
// minimum values for each type for positive-indexed array offsetting
private final byte MIN_BYTE_VALUE = -128; // signed 8-bit
private final byte MIN_CHAR_VALUE = 0; // unsigned 16-bit
private final short MIN_SHORT_VALUE = -32768; // signed 16-bit
/**
* Sorts a {@code byte[]} using counting sort. Sorts the parameter.
* @param array array to sort
*/
public void sort(byte[] array){
int len = array.length, s;
for(int i=-1; ++i < len; BYTE_SORT[array[i]-MIN_BYTE_VALUE]++);
for(int i=NUM_BYTE_VALUES, k=len; k > 0; ){
while((s = BYTE_SORT[--i]) == 0);
byte value = (byte)(i+MIN_BYTE_VALUE);
do {
array[--k] = value;
} while(--s > 0);
}
}
/**
* Sorts a {@code char[]} using counting sort. Sorts the parameter.
* @param array array to sort
*/
public void sort(char[] array){
int len = array.length, s;
for(int i=-1; ++i < len; CHAR_SORT[array[i]-MIN_CHAR_VALUE]++);
for(int i=NUM_CHAR_VALUES, k=len; k > 0; ){
while((s = CHAR_SORT[--i]) == 0);
char value = (char)(i+MIN_CHAR_VALUE);
do {
array[--k] = value;
} while(--s > 0);
}
}
/**
* Sorts a {@code short[]} using counting sort. Sorts the parameter.
* @param array array to sort
*/
public void sort(short[] array){
int len = array.length, s;
for(int i=-1; ++i < len; SHORT_SORT[array[i]-MIN_SHORT_VALUE]++);
for(int i=NUM_SHORT_VALUES, k=len; k > 0; ){
while((s = SHORT_SORT[--i]) == 0);
short value = (short)(i+MIN_SHORT_VALUE);
do {
array[--k] = value;
} while(--s > 0);
}
}
}The following is a basic implementation of the counting sort algorithms. Each array is instantiated to 100 random values, displayed, sorted, then displayed again.
import static java.lang.System.out;
import java.util.Random;
public class CountingSortTest {
public static void main(String args[]) {
CountingSort cs = new CountingSort();
Random r = new Random();
int size = 100;
byte b[] = new byte[size];
r.nextBytes(b);
out.println("Unsorted bytes: " + java.util.Arrays.toString(b));
cs.sort(b);
out.println("Sorted bytes: " + java.util.Arrays.toString(b));
char c[] = new char[size];
for (int i = -1; ++i < size; c[i] = (char) (r.nextInt(26) + 'a')); // lower
out.println("Unsorted chars: " + java.util.Arrays.toString(c));
cs.sort(c);
out.println("Sorted chars: " + java.util.Arrays.toString(c));
short s[] = new short[size];
for (int i = -1; ++i < size; s[i] = (short) (r.nextInt()));
out.println("Unsorted shorts: " + java.util.Arrays.toString(s));
cs.sort(s);
out.println("Sorted shorts: " + java.util.Arrays.toString(s));
}
}Output for the sample code. Note: the values are randomly generated, so your output will be different from mine:
Unsorted bytes: [-88, -123, 51, 125, 9, 39, -37, -6, 71, 89, 2, 60, -32, 17, 15, -85, -95, 58, 90, -69, -41, -116, 82, 92, -50, 113, -70, 67, 0, -38, 16, -55, 73, -17, -115, -85, -107, 105, -83, 50, 57, 22, 17, -69, -91, -70, -53, -13, 124, -118, 52, 11, -16, 58, -99, -107, -42, 18, -52, 84, 50, -110, 124, 51, -7, 89, 27, 43, 109, -110, 92, -110, 62, 61, -9, -20, -1, -75, 87, 1, 69, 118, -66, 31, 121, 117, 3, -84, -38, 84, -109, -27, -109, 34, 101, 77, -49, 0, 72, -101]
Sorted bytes: [-123, -118, -116, -115, -110, -110, -110, -109, -109, -107, -107, -101, -99, -95, -91, -88, -85, -85, -84, -83, -75, -70, -70, -69, -69, -66, -55, -53, -52, -50, -49, -42, -41, -38, -38, -37, -32, -27, -20, -17, -16, -13, -9, -7, -6, -1, 0, 0, 1, 2, 3, 9, 11, 15, 16, 17, 17, 18, 22, 27, 31, 34, 39, 43, 50, 50, 51, 51, 52, 57, 58, 58, 60, 61, 62, 67, 69, 71, 72, 73, 77, 82, 84, 84, 87, 89, 89, 90, 92, 92, 101, 105, 109, 113, 117, 118, 121, 124, 124, 125]
Unsorted chars: [l, k, t, k, v, b, w, c, x, a, l, n, u, h, r, q, v, o, z, w, n, e, q, h, o, j, e, k, v, d, j, u, p, r, v, o, x, s, a, r, i, e, n, u, m, r, o, j, f, w, i, z, b, i, l, d, r, v, p, s, k, v, s, t, x, z, w, v, c, z, u, a, n, n, r, d, y, e, x, s, u, n, c, t, t, s, g, c, n, v, u, y, u, c, a, t, h, g, l, y]
Sorted chars: [a, a, a, a, b, b, c, c, c, c, c, d, d, d, e, e, e, e, f, g, g, h, h, h, i, i, i, j, j, j, k, k, k, k, l, l, l, l, m, n, n, n, n, n, n, n, o, o, o, o, p, p, q, q, r, r, r, r, r, r, s, s, s, s, s, t, t, t, t, t, u, u, u, u, u, u, u, v, v, v, v, v, v, v, v, w, w, w, w, x, x, x, x, y, y, y, z, z, z, z]
Unsorted shorts: [28431, -27242, -15427, 30026, -13757, 9835, -18777, 30106, -10928, -29708, -19088, -10495, -19510, -31170, -21088, 24165, -25399, 17119, -26302, 4106, 2488, -15050, -1064, -25729, 32364, 3831, -17778, 8635, 15992, -13082, -15437, -18046, -31810, -29726, 14692, 22029, 2633, -17884, 5001, -3095, 1370, -1848, 27909, 12319, -11840, -32371, -4055, -21100, -1684, -23336, 5736, -4942, 23620, -23554, 12113, 31048, -28105, 27586, 25273, -27986, -9583, -3300, 8759, -19923, 11407, 16956, -16940, -27747, 15670, 26061, 4099, -23474, -29088, -11650, 29902, -981, -9449, -835, -32686, 17692, 29989, 10437, 10349, 13484, 26603, -18725, 21941, 31724, 29809, 28627, 4011, 20886, 15038, -27175, -18384, -1420, 9322, -17043, 2615, -3070]
Sorted shorts: [-32686, -32371, -31810, -31170, -29726, -29708, -29088, -28105, -27986, -27747, -27242, -27175, -26302, -25729, -25399, -23554, -23474, -23336, -21100, -21088, -19923, -19510, -19088, -18777, -18725, -18384, -18046, -17884, -17778, -17043, -16940, -15437, -15427, -15050, -13757, -13082, -11840, -11650, -10928, -10495, -9583, -9449, -4942, -4055, -3300, -3095, -3070, -1848, -1684, -1420, -1064, -981, -835, 1370, 2488, 2615, 2633, 3831, 4011, 4099, 4106, 5001, 5736, 8635, 8759, 9322, 9835, 10349, 10437, 11407, 12113, 12319, 13484, 14692, 15038, 15670, 15992, 16956, 17119, 17692, 20886, 21941, 22029, 23620, 24165, 25273, 26061, 26603, 27586, 27909, 28431, 28627, 29809, 29902, 29989, 30026, 30106, 31048, 31724, 32364]