Finding median from unsorted array with duplicate elements without sorting it 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.

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

int countFreq(int *array, int size_array, int item)
{
    int i, freq = 0;
    for(i = 0; i &lt; 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 &lt; 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 &lt; range + 1; i++)
    {
        addition += freq[i];
        if(addition &gt;= 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


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! 
I find it hard to digest the performance of this algorithm with larger arrays to sort, for now, this is O(n3) as far as I can think of.
If we never modify the elements of array, then it should be passed as a pointer to const: int const *array.

The frequency counts can be unsigned, and ought to be able to represent any size of input array (that suggests that count should be a size_t).

We absolutely must test that the return value of malloc() (and family) is not null before trying to dereference it (including passing it to memset()).  Additionally, it's not necessary or desirable to cast it to the target type:

size_t *freq = calloc(sizeof *freq, range + 1);
if (!freq) {
    fputs("Memory allocation failed!\n", stderr);
    exit(EXIT_FAILURE);
}


The algorithm has undefined behaviour if any element in the array is less than zero.  We need to find the minimum as well as maximum value, or perhaps change the input to be an unsigned type.

The counting is strange, with the nested loop.  Normally, we'd loop just once, incrementing the index for each element we look at - something like this:

for (int i = 0;  i &lt; count;  ++i) {
     ++freq[array[i]];
}


To avoid excessive temporary memory use for the count array, we could use a multi-pass approach.


Divide the range [min,max] into into (say) 256 buckets.
Count the inputs into those buckets.
Identify the median bucket.  Call that M.
Now divide the range represented by M into buckets.
Make another pass over the inputs, counting values within M into these new buckets (discarding values not in M).
Repeat until the bucket size is 1.