I reviewed some implementations of the median function in widely used statistics packages. They use simple flow like sorting the array and returning the middle element. The average runtime complexity of comparison-based sorting algorithms is linearithmic -> O(N log N)