You don't actually have to sort the array to find the median, just the nth order statistic use the std::nth_element function. Ex.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#include <algorithm>
int main(int argc, char* argv[])
{
// set up data some example data
std::vector<int> values(21);
for ( size_t i = 0; i < values.size(); ++i )
values[i] = i;
std::random_shuffle(value.begin(), values.end());
// use nth order statistic, only guarantees the nth element is correctly placed
int n = values.size()/2;
std::nth_element(values.begin(), values.begin() + n, values.end());
cout << "The median is : " << values[n] << std::endl;
return 0;
}