Thankyou for briefly explaining! I didn't know much about std::endl as I have just used it in college to break lines but this explanation is really nice! Also, I did not think of the range of int, good point! Virtual destructor, how did I miss that!

That's why I don't use namespaces, don't know why I did it here @L.F.

The default number of threads is the number of cores in your machine!

I tried it with random array and I feel it gets stuck in an infinite loop for some inputs. I'll figure out the cases and will post it here

You can find the source code here ndevilla.free.fr/median/median/src/torben.c

Just to keep a note, I was just mad at this, and how can such a simple problem does not have any efficient solution. Torben's Median Algorithm works charm, the main property of this algorithm is, "Bigger the array gets, better the algorithm becomes"! It dosen't sort the array. For odd number of elements, it returns the middle and for even it returns n/2 highest value. There is a slight improvement of this on github for even sized arrays to return actual median! Obviously it's better with O(log(N))

Wow! This significantly reduces the time required! Is that O(n)? I used Torben's method earlier which is O(log(N)) but this is even faster and much faster indeed! Can you throw some light on time complexity? I just changed the way to create a frequency array, did not incorporate any changes related to excessive temporary memory.