A counting sort function in C

I've tried to implement the counting sort algorithm in C.

What efficiencies can you spot?
I squint at the end when running through the original array again to assign it the sorted array. Maybe there is a better way?

/**
* Sorts array of n values.
* Using counting sort O(n)
*/
void sort(int values[], int n)
{
  //set our known max length, initialize our placer array and then our sorted array
  int maxLength = 65536;
  int placer[maxLength];
  int sorted[n];

  //so we can know which indexes in our placer array are in values array
  for ( int i = 0; i < n; i++ ) {
    placer[ values[i] ] += 1;
  }

  //store the sum of previous elements in each element at each index because this will give us the sorted position
  for (int i = 0; i < maxLength; i++ ) {
    placer[ i + 1 ] += placer[i];
  }

  //fill the sorted array with the values elements using the corresponding placer index
  for ( int i = 0; i < n; i++ ) {
    sorted[ placer[ values[i] ] - 1 ] = values[i];
    placer [ values[i] ] -= 1;

  }

  //set the unsorted values array to the sorted array
  for (int i = 0; i < n; i++) {
    values[i] = sorted[i];
  }
}

Off by one error

This loop goes over by 1 and writes past the last array element:

for (int i = 0; i < maxLength; i++ ) {
    placer[ i + 1 ] += placer[i];
  }

You could either stop the loop at maxLength - 1, or rewrite the loop to start at 1 like this:

for (int i = 1; i < maxLength; i++ ) {
    placer[i] += placer[i-1];
  }

Uninitialized variable causes crash

When I ran your program, it crashed due to an uninitialized variable, here:

int placer[maxLength];

Later on, you do placer[values[i]] += 1 without ever having cleared the placer array to zeros, so you can get garbage values in the array. You can fix this by clearing the array like this:

memset(placer, 0, sizeof(placer));

However, I recommend not using variable length arrays. One reason is that they are only optionally supported in the latest C standard. The other reason is that sometimes you can overflow your stack if you allocate a large variable length array. I would use calloc() here to allocate the counting array.

Simplify the function

It looks like you are using a version of counting sort that is used for radix sort, which needs to move elements around in the array. For a simple counting sort, you don't need to do that. After the counting pass, you can just fill in the original array with values from the counts, like this:

// Uses counting sort to sort an array which contains values in the
// range [0..65535].  The counting array is allocated using calloc() in
// order to avoid putting a large array on the stack.
void sort(int values[], int n)
{
    const int maxLength = 65536;
    int      *counts    = calloc(maxLength, sizeof(*counts));

    if (counts == NULL) {
        return;
    }

    for (int i = 0; i < n; i++) {
        counts[values[i]]++;
    }

    int outIndex = 0;
    for (int i = 0; i < maxLength; i++) {
        for (int j = 0; j < counts[i]; j++) {
            values[outIndex++] = i;
        }
    }

    free(counts);
}

StackExchange Code Review Q#156543, answer score: 2