C++ parallel merge sort I'm a first year computer engineering student who's learning about algorithms and data structures. I've implemented a parallel merge sort algorithm in C++ and would like constructive criticism. This was done in Visual Studio on Windows.

Some thoughts:


portability isn't a concern I have atm.
merge_sort isn't using tail recursion, which I would like it to do





includes:
#include &lt;thread&gt;


function merge:

template&lt;typename T&gt;
void merge(T sequence[], int size)
{
    T* sorted = new T[size];
    int middle = size / 2;

    int index_left = 0;
    int index_right = middle;
    int index_sequence = 0;

    while (index_left &lt; middle &amp;&amp; index_right &lt; size)
    {
        if (sequence[index_left] &lt; sequence[index_right])
            sorted[index_sequence++] = sequence[index_left++];
        else
            sorted[index_sequence++] = sequence[index_right++];
    }

    while (index_left &lt; middle)
        sorted[index_sequence++] = sequence[index_left++];

    while (index_right &lt; size)
        sorted[index_sequence++] = sequence[index_right++];

    for (int i = 0; i &lt; size; i++)
        sequence[i] = sorted[i];

    delete[] sorted;
}



function merge_sort:

template&lt;typename T, int min_size_to_thread = 10000&gt;
void merge_sort(T sequence[], int size)
{
    if (size &gt; 1)
    {
        int middle = size / 2;
        if (size &gt; min_size_to_thread)
        {
            std::thread left(merge_sort&lt;T, min_size_to_thread&gt;, &amp;sequence[0], middle);
            std::thread right(merge_sort&lt;T, min_size_to_thread&gt;, &amp;sequence[middle], size - middle);
            left.join();
            right.join();
        }
        else
        {
            merge_sort&lt;T, min_size_to_thread&gt;(&amp;sequence[0], middle);
            merge_sort&lt;T, min_size_to_thread&gt;(&amp;sequence[middle], size - middle);
        }
        merge&lt;T&gt;(sequence, size);
    }
}




For those who are interested: I Did some performance testing on a i5-2530M 2.50Ghz (2 cores).
The sequence to merge sort is int[100000]



Edit:

I made merge_sort and merge take a T tmp[]. And I made a "wrapper" function around merge_sort like this:  

template&lt;typename T&gt;
void merge_sort(T* sequence, int size)
{
    T* tmp = new T[size];
    _merge_sort(sequence, tmp, size);
    delete[] tmp;
}


Now new is only called once. The "old" merge_sort is renamed to _merge_sort.
You would hava a) thread-pools so that the code won't spawn a new thread on each sub-sort, b) a limit on the number of sorts split into threads so that there isn't a new thread spawned for a low number of elements and c) a single array where all the sorting takes place and which is paritioned like a stack among the sort-threads (afaik the whole length should be two times the size of the array).

That would be a much of work to gain an efficient implementation.