Implement counting sort - EPI

Implement counting sort

http://www.growingwiththeweb.com/2014/05/counting-sort.html
It runs in O(n + k)O(n+k) time where nn is the number of elements to be sorted and kk is the number of possible values in the range.

Primitives, objects and duplicates
The basic algorithm can be augmented depending on the situation. For example when sorting primitives, you likely don’t care about retaining the original reference or stability of duplicates so the auxiliary array can be used to count instances of the value which can be reconstructed after.

However, sorting objects where there can be duplicates will require a more sophisticated method of storing values in the auxiliary array, such as a linked list or dynamic array.

The range of elements is known
Most of the elements in the range are present

If the list is known to be partially sorted then another option such as insertion sort may end up being better, since counting sort does not take advantage of that.

public class CountingSort {
    public static void sort(Integer[] array) {
        if (array.length == 0) {
            return;
        }

        // Determine minimum and maximum values
        Integer minValue = array[0];
        Integer maxValue = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < minValue) {
                minValue = array[i];
            } else if (array[i] > maxValue) {
                maxValue = array[i];
            }
        }

        sort(array, minValue, maxValue);
    }

    public static void sort(Integer[] array, int minValue, int maxValue) {
        int[] buckets = new int[maxValue - minValue + 1];

        for (int i = 0; i < array.length; i++) {
            buckets[array[i] - minValue]++;
        }

        int sortedIndex = 0;
        for (int i = 0; i < buckets.length; i++) {
            while (buckets[i] > 0) {
                array[sortedIndex++] = i + minValue;
                buckets[i]--;
            }
        }
    }
}

CountingSort.java
  public static void countingSort(ArrayList<Person> people) {
    Map<Integer, Integer> keyToCount = new HashMap<>();
    for (Person p : people) {
      if (keyToCount.containsKey(p.key)) {
        keyToCount.put(p.key, keyToCount.get(p.key) + 1);
      } else {
        keyToCount.put(p.key, 1);
      }
    }
    Map<Integer, Integer> keyToOffset = new HashMap<>();
    int offset = 0;
    for (Map.Entry<Integer, Integer> kc : keyToCount.entrySet()) {
      keyToOffset.put(kc.getKey(), offset);
      offset += kc.getValue();
    }

    while (!keyToOffset.isEmpty()) {
      Map.Entry<Integer, Integer> from = keyToOffset.entrySet().iterator()
          .next();
      Integer toKey = people.get(from.getValue()).key;
      Integer toValue = keyToOffset.get(toKey);
      Collections.swap(people, from.getValue(), toValue);
      // Use key_to_count to see when we are finished with a particular key.
      Integer count = keyToCount.get(toKey) - 1;
      keyToCount.put(toKey, count);
      if (count > 0) {
        keyToOffset.put(toKey, toValue + 1);
      } else {
        keyToOffset.remove(toKey);
      }
    }
  }