Counting Sort

Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to compute an item’s index in the final, sorted array. Counting sort assumes that each of the n input elements in a list has a key value ranging from 0 to k, for some integer k. For each element in the list, counting sort determines the number of elements that are less than it. Counting sort can use this information to place the element directly into the correct slot of the output array.

// Counting sort which takes negative numbers
void countSort(vector <int>& arr) 
{
  int max    = *max_element(arr.begin(), arr.end()); 
  int min    = *min_element(arr.begin(), arr.end()); 
  int range  = max - min + 1; 
  
  vector<int> count(range), output(arr.size()); 

  // Count of each unique object.
  for(int i = 0; i < arr.size(); i++) 
    count[arr[i]-min]++; 
  
  // Update array such that each element at each index stores the sum of previous counts. 
  for(int i = 1; i < count.size(); i++) 
    count[i] += count[i-1]; 
  
  // The modified count array indicates the position of each object in the output sequence.
  for(int i = arr.size()-1; i >= 0; i--) 
  { 
    output[count[arr[i]-min] -1] = arr[i]; 
    count[arr[i]-min]--; 
  } 
  
  for(int i=0; i < arr.size(); i++) 
      arr[i] = output[i]; 
}

int main() 
{ 
  vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10}; 
  countSort (arr);
}