find median with minimum time in an array

Question

I have an array lets say a = { 1,4,5,6,2,23,4,2}; now I have to find median of array position from 2 to 6 (odd total terms), so what I have done, I have taken a[1] to a[5] in arr[0] to arr[4] then I have sorted it and write the arr[2] as the median .

But here every time I put values from one array to another, so that the values of my initial array remains the same. Secondly, I have sorted, so this procedure is taking pretty much **time**. So I want to know if there is any way I can do this differently to reduce my computation time.

Any websites, material to understand, what, and how to do?

Answer 1

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

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

Answer 2

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