QtConcurrent: use nth_element to calculate the (correct) median

Sorting is O(NlogN) complexity, while nth_element is linear.
Also remove the errornous +1 when calculating the median position.

Change-Id: Ib39085b59a6c5d15a3a940b1ce3377080340bc09
Reviewed-by: Olivier Goffart <ogoffart@woboq.com>

1 files changed, 4 insertions, 3 deletions

diff --git a/src/concurrent/qtconcurrentmedian.h b/src/concurrent/qtconcurrentmedian.h
index 9079393388..b39b3ed32b 100644
--- a/src/concurrent/qtconcurrentmedian.h
+++ b/src/concurrent/qtconcurrentmedian.h
@@ -102,9 +102,10 @@ public:
     {
         if (dirty) {
             dirty = false;
-            QVector<T> sorted = values;
-            std::sort(sorted.begin(), sorted.end());
-            currentMedian = sorted.at(bufferSize / 2 + 1);
+            QVector<T> copy = values;
+            typename QVector<T>::iterator begin = copy.begin(), mid = copy.begin() + bufferSize/2, end = copy.end();
+            std::nth_element(begin, mid, end);
+            currentMedian = *mid;
         }
         return currentMedian;
     }