Uma outra versão da ideia do Lelzin

rangesort.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <assert.h>

#define SIZE(ARR) (sizeof(ARR)/sizeof(ARR[0]))
#define DEFAULT(STRUC) (STRUC){0}

#define ALLOC(TYPE,LEN) \
    (TYPE*)calloc(LEN, sizeof(TYPE))

#define VOIDGET(TYPE,ARRAY,POSITION) \
    ( (void*)(ARRAY) + ((POSITION)*sizeof(TYPE)) )

#define GET(TYPE,ARRAY,POSITION) \
  (TYPE*)VOIDGET(TYPE,ARRAY,POSITION)

#define PUTPTR(TYPE,ARRAY,POSITION,VALUE) \
    (TYPE*)memcpy(VOIDGET(TYPE,ARRAY,POSITION), VALUE, sizeof(TYPE))

#define PUT(TYPE,ARRAY,POSITION,VALUE) \
  *GET(TYPE,ARRAY,POSITION) = (VALUE)

struct MinMax { int min; int max; };

struct MinMax IntArray_MinMax (size_t size, int arr[static size]) {
  assert(size >= 2);
  struct MinMax mm = (struct MinMax) {.min = arr[0], .max = arr[0]};
  for (size_t p = 1; p < size; p++) {
    if (arr[p] < mm.min) { mm.min = arr[p]; }
    if (arr[p] > mm.max) { mm.max = arr[p]; }
  }
  return mm;
}

struct IntFreqs {
  struct MinMax mm;
  size_t *freqs;
};

size_t IntFreqs_RangeSize (int min, int max) {
  assert(max >= min);
  return max - min + 1;
}

struct IntFreqs IntFreqs_Alloc (struct MinMax *mm) {
  size_t rangeSize = IntFreqs_RangeSize(mm->min, mm->max);
  size_t *freqs = ALLOC(size_t, rangeSize);
  if (freqs == NULL) { return DEFAULT(struct IntFreqs); }
  struct IntFreqs ifreq = (struct IntFreqs) {.mm = *mm, .freqs = freqs};
  return ifreq;
}

void IntFreqs_Destroy (struct IntFreqs *ifreq) {
  free(ifreq->freqs);
  ifreq->freqs = NULL;
  ifreq->mm = DEFAULT(struct MinMax);
}

void IntFreqs_Populate (struct IntFreqs *ifreq, size_t size, int arr[static size]) {
  assert(size >= 2);
  int min = ifreq->mm.min;
  size_t rangeSize = IntFreqs_RangeSize(ifreq->mm.min, ifreq->mm.max);
  for (size_t p = 0; p < size; p++) {
    int qq = arr[p] - min; assert(qq >= 0);
    size_t q = (size_t) qq; assert(q < rangeSize);
    //ifreq->freqs[q] += 1;
    *GET(size_t, ifreq->freqs, q) += 1;
  }
}

void IntFreqs_Print (struct IntFreqs *ifreq) {
  int min = ifreq->mm.min;
  int max = ifreq->mm.max;
  size_t rangeSize = IntFreqs_RangeSize(min, max);
  printf("<IntFreqs: min=%d max=%d> {", min, max);
  for (size_t p = 0; p < rangeSize-1; p++) {
    //printf("%lu ", ifreq->freqs[p]);
    printf("%lu ", *GET(size_t, ifreq->freqs, p));
  }
  //printf("%lu}\n", ifreq->freqs[rangeSize-1]);
  printf("%lu}\n", *GET(size_t, ifreq->freqs, rangeSize-1));
}

struct IntFreqSample {
  int value;
  size_t freq;
};

size_t IntFreqs_SamplesQuantity (struct IntFreqs *ifreq) {
  size_t rangeSize = IntFreqs_RangeSize(ifreq->mm.min, ifreq->mm.max);
  size_t q = 0;
  for (size_t p = 0; p < rangeSize; p++) {
    //if (ifreq->freqs[p] > 0) { q += 1; }
    size_t freq = *GET(size_t, ifreq->freqs, p);
    if (freq > 0) { q += 1; }
  }
  assert(q >= 1);
  return q;
}

struct IntFreqSparse {
  struct MinMax mm;
  size_t quantity;
  struct IntFreqSample *samples;
};

struct IntFreqSparse IntFreqSparse_Alloc (struct MinMax *mm, size_t quantity) {
  assert(quantity >= 1);
  assert(quantity <= IntFreqs_RangeSize(mm->min, mm->max));
  struct IntFreqSample *s = ALLOC(struct IntFreqSample, quantity);
  if (s == NULL) { return DEFAULT(struct IntFreqSparse); }
  struct IntFreqSparse freqsparse = (struct IntFreqSparse) {.mm = *mm, .quantity = quantity, .samples = s};
  return freqsparse;
}

void IntFreqSparse_Destroy (struct IntFreqSparse *ifreqs) {
  free(ifreqs->samples);
  ifreqs->samples = NULL;
  ifreqs->quantity = 0;
  ifreqs->mm = DEFAULT(struct MinMax);
}

void IntFreqSparse_Populate (struct IntFreqSparse *ifreqs, struct IntFreqs *ifreq) {
  assert(ifreqs->samples != NULL);
  int min = ifreq->mm.min;
  int max = ifreq->mm.max;
  assert(ifreqs->mm.min == min && ifreqs->mm.max == max);
  size_t rangeSize = IntFreqs_RangeSize(min, max);
  size_t quantity = ifreqs->quantity;
  assert(quantity == IntFreqs_SamplesQuantity(ifreq));
  assert(quantity <= rangeSize);
  size_t r = 0;
  for (size_t p=0; p<quantity; p++) {
    //while (r < rangeSize && ifreq->freqs[r] == 0) { r += 1; }
    while (r < rangeSize && *GET(size_t, ifreq->freqs, r) == 0) { r += 1; } assert(r >= p);
    int value = (int) (r + min); assert(value <= max);
    size_t freq = *GET(size_t, ifreq->freqs, r);
    //ifreqs->samples[p] = (struct IntFreqSample) {.value = value, .freq = freq};
    struct IntFreqSample sample = (struct IntFreqSample) {.value = value, .freq = freq};
    PUT(struct IntFreqSample, ifreqs->samples, p, sample);
    r += 1;
  }
  assert(r <= rangeSize);
}

void IntFreqSparse_Print (struct IntFreqSparse *ifreqs) {
  int min = ifreqs->mm.min;
  int max = ifreqs->mm.max;
  size_t q = ifreqs->quantity;
  printf("<IntFreqSparse: min=%d max=%d> {", min, max);
  struct IntFreqSample *s;
  for (size_t p = 0; p < q-1; p++) {
    s = GET(struct IntFreqSample, ifreqs->samples, p);
    printf("{%d x %lu} ", s->value, s->freq);
  }
  s = GET(struct IntFreqSample, ifreqs->samples, q-1);
  printf("{%d x %lu}}\n", s->value, s->freq);
}

void testIt (size_t size, int arr[static size]) {
  struct MinMax mm = IntArray_MinMax(size, arr);
  struct IntFreqs ifreq = IntFreqs_Alloc(&mm);
  IntFreqs_Populate(&ifreq, size, arr);
  IntFreqs_Print(&ifreq);
  size_t quantity = IntFreqs_SamplesQuantity(&ifreq);
  struct IntFreqSparse ifreqs = IntFreqSparse_Alloc(&mm, quantity);
  IntFreqSparse_Populate(&ifreqs, &ifreq);
  IntFreqSparse_Print(&ifreqs);
  IntFreqs_Destroy(&ifreq);
  IntFreqSparse_Destroy(&ifreqs);
}

int main (void) {
  int t1[] = {13,9,9,8,8,7,7,6,6,6,-4};
  assert(SIZE(t1) == 11);
  int t2[] = {-2,2};
  testIt(SIZE(t1), t1);
  testIt(SIZE(t2), t2);
  return 0;
}