Counting sort algorithm (https://en.m.wikipedia.org/wiki/Counting_sort)

couning_sort.c

// Counting sort algorithm
// https://en.m.wikipedia.org/wiki/Counting_sort
//
// Build clang:
//   clang -Wall -Wextra -Wpedantic -g counting_sort.c -o counting_sort
//
// Build gcc:
//   gcc -Wall -Wextra -Wpedantic -g counting_sort.c -o counting_sort

typedef int i32;

#define LIKELY(x)   __builtin_expect((x), 1)
#define UNLIKELY(x) __builtin_expect((x), 0)

// Debug and Release assert
static inline void assert_msg(i32 condition, const char *msg) {
  if (UNLIKELY(!condition)) {
    __builtin_printf("%s\n", msg);

    // __debugbreak and __builtin_debugtrap() would allow SIGTRAPping into a debugger
    // __builtin_trap generates SIGILL and code after it will be optmized away.
#if defined(_MSC_VER)
    __debugbreak();
#elif defined(__clang__)
    __builtin_debugtrap();
#else
    __builtin_trap(); // gcc doesn't have __builtin_debugtrap equivalent
#endif
  }
}

#define STR1(s) # s
#define STR(s) STR1(s)

#define ASSERT(condition) assert_msg(!!(condition), \
    __FILE__ ":" STR(__LINE__) ": (" STR(condition) ") expected to be true\n")

// Sort array of i32 using counting sort algorithm in ascending order.
// https://en.m.wikipedia.org/wiki/Counting_sort
// Best suited for arrays wich values range is smaller than element count N.
// Uses `index_size` memory for index.
// in_out_array - array to sort.
// in_out_index - auxiliary array to keep index for sorting. Will be zeroed out
//                before sorting.
// [value_min, value_max) - range of values in the array.
// value_min    - minimum value of an array
// value_max    - maximum value of an array is calculated as
//                (value_min + index_size)
void sort_counting_i32(i32 *in_out_arr, i32 arr_size, i32 *in_out_index, i32 index_size,
    i32 arr_value_min) {
  if (LIKELY(arr_size > 0 || index_size > 0 || in_out_arr || in_out_index))
  {
    // Count frequenices of values in the array
    i32 arr_value_max = arr_value_min + index_size;

    for (i32 i = 0; i < index_size; ++i) {
      in_out_index[i] = 0;
    }

    for (i32 i = 0; i < arr_size; ++i) {
      i32 v = in_out_arr[i];
      i32 index_i = v - arr_value_min;
      ASSERT(index_i >= 0);
      ASSERT(index_i < index_size);
      ++in_out_index[index_i];
    }

    // Traditional implementation first makes cummulative frequency index
    // (freq(N+1) = freq(N) + freq(N+1). Then it iterates backwards
    // over array, decrementing frequency in frequency index for the
    // value at array[i].
    // This implementation just goes straight over the index.
    // It could be less efficient in case index is much larget than array.
    i32 arr_i = 0;
    for (i32 index_i = 0; index_i < index_size; ++index_i) {
      i32 freq = in_out_index[index_i];
      for (i32 i = 0; i < freq; ++i) {
        in_out_arr[arr_i++] = index_i + arr_value_min;
      }
    }
  }
}

// Test
i32 is_equal_arrs_i32(i32 *a, i32 *b, i32 size) {
  for (i32 i = 0; i < size; ++i) {
    if (a[i] != b[i])
    {
      return 0;
    }
  }
  return 1;
}

int main(void) {
  {
    sort_counting_i32(0, 0, 0, 0, 0);
  }

  {
    i32 arr[] = { 10 };
    i32 arr_size = sizeof(arr) / sizeof(arr[0]);

    enum { INDEX_SIZE = 1 };
    i32 index[INDEX_SIZE] = {0};

    sort_counting_i32(arr, arr_size, index, INDEX_SIZE, 10);

    i32 expected_arr[] = {10};
    ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size));
  }

  {
    i32 arr[] = { 0, 1, 2, 3 };
    i32 arr_size = sizeof(arr) / sizeof(arr[0]);

    enum { INDEX_SIZE = 4 };
    i32 index[INDEX_SIZE] = {0};

    sort_counting_i32(arr, arr_size, index, INDEX_SIZE, 0);

    i32 expected_arr[] = {0, 1, 2, 3};
    ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size));
  }

  {
    i32 arr[] = { 3, 2, 1, 0, -1, -2, -3 };
    i32 arr_size = sizeof(arr) / sizeof(arr[0]);

    enum { INDEX_SIZE = 7 };
    i32 index[INDEX_SIZE] = {0};

    sort_counting_i32(arr, arr_size, index, INDEX_SIZE, -3);

    i32 expected_arr[] = {-3, -2, -1, 0, 1, 2, 3};
    ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size));
  }

  {
    i32 arr[] = { 30, 2, 1, 0, -1, -2, -30 };
    i32 arr_size = sizeof(arr) / sizeof(arr[0]);

    enum { INDEX_SIZE = 61 };
    i32 index[INDEX_SIZE] = {0};

    sort_counting_i32(arr, arr_size, index, INDEX_SIZE, -30);

    i32 expected_arr[] = {-30, -2, -1, 0, 1, 2, 30};
    ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size));
  }

  {
    i32 arr[] = { 30, 30, 2, 1, 0, 0, -1, -2, -2, -2, -2, -30, -30 };
    i32 arr_size = sizeof(arr) / sizeof(arr[0]);

    enum { INDEX_SIZE = 61 };
    i32 index[INDEX_SIZE] = {0};

    sort_counting_i32(arr, arr_size, index, INDEX_SIZE, -30);

    i32 expected_arr[] = {-30, -30, -2, -2, -2, -2, -1, 0, 0, 1, 2, 30, 30};
    ASSERT(is_equal_arrs_i32(arr, expected_arr, arr_size));
  }

  return 0;
}