I am implementing a method to find the median of an unsorted array using a counting sort. I would happily go for a median of medians or selection algorithm for better performance but they are essentially sorting the array(or partially sorting the array if I choose to go for minHeap) which I am not in favor of.

The code I wrote goes like this

int getRange(int *array, int count)
{
    int i, max = 0;
    for(i = 0; i < count; i++)
    {
        if(array[i] > max)
        {
            max = array[i];
        }
    }
    return max;
}

int countFreq(int *array, int size_array, int item)
{
    int i, freq = 0;
    for(i = 0; i < size_array; i++)
    {
        if(array[i] == item)
            freq++;
    }
    return freq;
}

int median(int *array, int count)
{
    int range = getRange(array, count);
    int i, mid_index, addition = 0;

    //Yes I can use calloc here
    int *freq = (int *)malloc(sizeof(int) * range + 1);
    memset(freq, 0, sizeof(int)* range + 1);

    for(i = 0; i < range + 1; i++)
    {
        //Count i in array and insert at freq[i]
        freq[i] = countFreq(array, count, i);
    }

    if(count % 2 == 0)
    {
        mid_index = count / 2;
    }
    else
    {
        mid_index = count / 2 + 1;
    }

    for(i = 0; i < range + 1; i++)
    {
        addition += freq[i];
        if(addition >= mid_index)
        {
            break;
        }
    }
    free(freq);
    return i;
}

I followed this answer to implement using C! Certainly, I want to improve upon this or maybe a better algorithm that doesn't sort the array! For me, this algorithm has some problems

1. What if there are just 2 elements say {10, 10000}, this will still go on for creating an array of size 10000 which essentially has zeros in it except at the last index!

2. I find it hard to digest the performance of this algorithm with larger arrays to sort, for now, this is O(n^3) as far as I can think of