Find median of N 8-bit numbers

Question

Given an array of N 8-bit numbers ( value 0-255)?

How to find the median?

I have tried radix sort and median of medians algorithms.

Is there a better way given the values of the numbers are between 0 and 255?

Answer 1

Use something similar to counting sort.

• Create a "counts" array of size 256, initialized to all 0's. counts[x] will be the number of times x appears in the input array.
• Iterate over your input array incrementing the value in the position in the counts array corresponding to each value in the input array (so counts[input[i]]++).
• Loop over the counts array, summing all the values until you get to half the total number of values. The index will be the number we're looking for (some additional logic needed to deal with an even number of values).

This runs in O(n) time using O(1) space (which is asymptotically optimal).

So something like: (pseudo-code)

// Count the number of occurrences of each value.
counts[256] = {0}
for i = 0 to input.length
   counts[input[i]]++

// Get the median.
count = input.length
sum = 0
if count divisible by 2
   first = NaN
   for i = 0 to counts.length
      sum += counts[i]
      if first == NaN && sum >= count / 2
         first = i
      if sum >= count / 2 + 1
         median = (first + i) / 2
         break
else
   for i = 0 to counts.length
      sum += counts[i]
      if sum >= (count + 1) / 2
         median = i
         break
return median

---

There are other ways to achieve the same time and space complexity (albeit a bit more complex than the above, and requiring you to modify the input array):

• A variant of quick sort which is optimized for duplicate values by splitting the array into 3 instead of 2 at each step (smaller, equal and larger values).

• A variant of radix sort which is in-place.

• The median of medians algorithm also in fact shares this complexity.