find median with minimum time in an array

Use std::nth_element from <algorithm> which is O(N):

nth_element(a, a + size / 2, a + size);
median = a[size/2];

It is possible to find the median without sorting in O(n) time; algorithms that do this are called selection algorithms.

If you are doing multiple queries on the same array then you could use a Segment Tree. They are generally used to do range minimum/maximum and range sum queries but you can change it to do range median.

A segment tree for a set with n intervals uses O(n log n) storage and can be built in O(n log n) time. A range query can be done in O(log n).

Example of median in range segment tree:

You build the segment tree from the bottom up (update from the top down):

                    [5]
        [3]                     [7]
 [1,2]        [4]         [6]         [8] 
1     2     3     4     5     6     7     8

Indices covered by node:

                    [4]
        [2]                     [6]
 [0,1]        [3]         [5]         [7] 
0     1     2     3     4     5     6     7

A query for median for range indices of 4-6 would go down this path of values:

                    [4]
                          [5]
0     1     2     3     4     5     6     7

Doing a search for the median, you know the number of total elements in the query (3) and the median in that range would be the 2nd element (index 5). So you are essentially doing a search for the first node which contains that index which is node with values [1,2] (indices 0,1).

Doing a search of the median of the range 3-6 is a bit more complicated because you have to search for two indices (4,5) which happen to lie in the same node.

                    [4]
                                [6]
                          [5] 
0     1     2     3     4     5     6     7

Segment tree

Range minimum query on Segment Tree

To find the median of an array of less than 9 elements, I think the most efficient is to use a sort algorithm like insertion sort. The complexity is bad, but for such a small array because of the k in the complexity of better algorithms like quicksort, insertion sort is very efficient. Do your own benchmark but I can tell you will have better results with insertion sort than with shell sort or quicksort.