What is the key to implement multi thread sorting algorithm efficient? The naive implementations doesn't work properly
<p>My first version two thread selection sort starts a new thread for every iteration.</p>

<p>Some comparison(left - one thread, right - two thread version, time - ms):</p>

<pre><code>Size: 500       time 1  time 5
Size: 1000      time 1  time 9
Size: 1500      time 4  time 12
Size: 2000      time 5  time 16
Size: 2500      time 10 time 22
Size: 3000      time 14 time 26
Size: 3500      time 19 time 30
Size: 4000      time 24 time 36
Size: 4500      time 30 time 43
Size: 5000      time 37 time 49
Size: 5500      time 46 time 57
Size: 6000      time 55 time 66
Size: 6500      time 63 time 76
Size: 7000      time 74 time 80
Size: 7500      time 85 time 92
Size: 8000      time 96 time 102
Size: 8500      time 108        time 109
Size: 9000      time 122        time 124
Size: 9500      time 135        time 132
Size: 10000     time 150        time 144
Size: 10500     time 165        time 156
Size: 11000     time 181        time 174
Size: 11500     time 200        time 177
Size: 12000     time 218        time 195
Size: 12500     time 235        time 205
Size: 13000     time 255        time 214
Size: 13500     time 273        time 226
Size: 14000     time 296        time 245
</code></pre>

<p>After 9500 size array two threads work faster. 
In my second implementation a thread start once. But it has so unbelievable performance.</p>

<p>My cpu has 4 cores.</p>

<pre><code>Size: 0 time 0  time 0
Size: 50        time 0  time 151
Size: 100       time 0  time 1276
Size: 150       time 0  time 2089
Size: 200       time 0  time 3925
Size: 250       time 0  time 5303
</code></pre>

<p>Code:</p>

<pre><code>//one thread
template&lt;class ItType&gt;
void selectionSortThreadsHelper2(ItType beg, ItType end)
{
    //sorting element by element
    for (auto it = beg; it != end; ++it) {

        ItType middleIt = it + std::distance(it, end) / 2;

        auto search = [&amp;] { return std::min_element(it, middleIt); };
        //search
        std::future&lt;ItType&gt; minFirstHalfResult(std::async(std::launch::async , search));

        //wait searching
        ItType minSecondHalfIt = std::min_element(middleIt, end);
        ItType minFirstHalfIt = minFirstHalfResult.get();

        //swap if
        ItType minIt = *minFirstHalfIt &lt; *minSecondHalfIt ? minFirstHalfIt : minSecondHalfIt;
        if (minIt != it)
            std::iter_swap(minIt, it);
    }
}

//two thread
template&lt;class ItType&gt;
void selectionSortThreadsHelper3(ItType beg, ItType end)
{
    bool quit = false;
    bool readyFlag = false;
    bool processed = false;
    std::mutex readyMutex;
    std::condition_variable readyCondVar;

    ItType it;
    ItType middleIt;
    ItType minFirstHalfIt;
    auto search = [&amp;]() {
        while (true) {
            std::unique_lock&lt;std::mutex&gt; ul(readyMutex);
            readyCondVar.wait(ul, [&amp;] {return readyFlag; });

            if (quit)
                return;

            minFirstHalfIt = std::min_element(it, middleIt);

            processed = true;

            ul.unlock();
            readyCondVar.notify_one();
        }
    };

    std::future&lt;void&gt; f(std::async(std::launch::async, search));

    //sorting element by element
    for (it = beg; it != end; ++it) {

        middleIt = it + std::distance(it, end) / 2;

        //say second thread to start searching
        {
            std::lock_guard&lt;std::mutex&gt; lg(readyMutex);
            readyFlag = true;
        }
        readyCondVar.notify_one();
        //std::this_thread::yield();

        ItType minSecondHalfIt = std::min_element(middleIt, end);

        //wait second thread
        {
            std::unique_lock&lt;std::mutex&gt; ul(readyMutex);
            readyCondVar.wait(ul, [&amp;] { return processed; });
            processed = false;
            readyFlag = false;
        }
        readyCondVar.notify_all();

        //swap if
        ItType minIt = *minFirstHalfIt &lt; *minSecondHalfIt ? minFirstHalfIt : minSecondHalfIt;
        if (minIt != it)
            std::iter_swap(minIt, it);
    }

    //quit thread
    {
        std::lock_guard&lt;std::mutex&gt; lg(readyMutex);
        readyFlag = true;
        quit = true;
    }
    readyCondVar.notify_all();

    f.get();
}
</code></pre>