Implementation of Merge Sort in C++ I'd originally not copied the result vector to vec which I figured and corrected. Iis there a better way to implement the merge sort other than the approach I've taken?

template&lt;typename T&gt; void merge(std::vector&lt;T&gt; &amp;vec, int left, int mid, int right )
{
    int i=left;
    int j=mid+1;
    int k=0;
    int size = (right - left) +1;
    std::vector&lt;T&gt; result(size);

    while(i &lt;= mid &amp;&amp; j &lt;= right)  result[k++] = (vec[i] &lt; vec[j])? vec[i++] : vec[j++];
    while(i &lt;= mid)                result[k++] = vec[i++];
    while(j &lt;= right)              result[k++] = vec[j++];

    for(k=0; k &lt; size; k++)
    {
        vec[left+k] = result[k];
    }
}

template&lt;typename T&gt; void mergeSort(std::vector&lt;T&gt; &amp;vec, int left, int right)
{
    // Base Case --- Left is greater than right, then don't execute.

    if (left&lt;right){

        // get mid point.
        int mid = left + (right-left)/2 ;
        // recursive merge sort until array(half) is 1 in length.
        mergeSort(vec, left, mid);
        mergeSort(vec, mid+1, right);
        // merge both arrays.
        merge(vec, left, mid, right);
    }
}


main():

int main()
{
    vector&lt;int&gt; v{14,3,2,5,10};
    //bubbleSort(v);
    //selectionSort(v);
    mergeSort(v, 0, v.size()-1);
    printVec(v);


    return 0;
}


I'm trying to figure out space optimization considerations. Currently, the space is \$O(N)\$ (since I'm creating a resultant array in merge which creates a max size of N? Please correct me if I'm wrong here.)
Instability

while(i &lt;= mid &amp;&amp; j &lt;= right)  result[k++] = (vec[i] &lt; vec[j])? vec[i++] : vec[j++];


Whenever vec[i] == vec[j], the above excerpt from your code will favour the element from the right chunk, which reorders equal elements. Instead you should say:

while(i &lt;= mid &amp;&amp; j &lt;= right)  result[k++] = (vec[i] &lt;= vec[j])? vec[i++] : vec[j++];


or even:

while(i &lt;= mid &amp;&amp; j &lt;= right)  result[k++] = (vec[j] &lt; vec[i])? vec[j++] : vec[i++];


Misc 1

while(i &lt;= mid)                result[k++] = vec[i++];
while(j &lt;= right)              result[k++] = vec[j++];


You could use std::copy from algorithm header file to do the above; it might be (or might not) be optimized for speed.

Misc 2

Actually, there is std::merge in algorithm; why not use it?

API

At this point, your implementation is restricted to std::vector. It is not hard to make it accept any sequence:

template&lt;typename RandIt1, typename RandIt2&gt;
void mergeSort(RandIt1 source_begin,
               RandIt1 source_end,
               RandIt2 target_begin,
               RandIt2 target_end)
{
    auto range_length = std::distance(source_begin, source_end);

    if (range_length &lt; 2)
    {
        return;
    }

    auto left_subrange_length = range_length &gt;&gt; 1;

    mergeSort(target_begin,
              target_begin + left_subrange_length,
              source_begin,
              source_begin + left_subrange_length);

    mergeSort(target_begin + left_subrange_length,
              target_end,
              source_begin + left_subrange_length,
              source_end);

    std::merge(source_begin,
               source_begin + left_subrange_length,
               source_begin + left_subrange_length,
               source_end,
               target_begin);
}

template&lt;typename RandIt&gt;
void mergeSort(RandIt begin, RandIt end)
{
    auto range_length = std::distance(begin, end);

    if (range_length &lt; 2)
    {
        return;
    }

    using value_type = typename std::iterator_traits&lt;RandIt&gt;::value_type;
    std::vector&lt;value_type&gt; aux(begin, end);
    mergeSort(aux.begin(), aux.end(), begin, end);
}

template&lt;typename T&gt;
void mergeSort(std::vector&lt;T&gt;&amp; vec)
{
    mergeSort(vec.begin(), vec.end());
}


Hope that helps.

Peformance

In this Gist you can get everything needed for a performance demonstration. I get the following figures:



OP mergeSort in 3511 milliseconds.
cr mergeSort in 1653 milliseconds.
stable_sort in 1332 milliseconds.
Algorithms agree: true



Space consideration

At any given instant, you have \$\Theta(N)\$ worth memory allocated. However, if you count all std::vector&lt;T&gt; result(size);, you will get \$\Theta(N \log N)\$ worth memory allocated. 

You can do better. You can allocate a vector that is of the same length and content as the input vector. Then, you merge from one vector to another; and at the next recursion level you swap their roles and so on. That way, you can eliminate

for(k=0; k &lt; size; k++)
{
    vec[left+k] = result[k];
}


in the merging function.

Suppose also that we are sorting 8 elements. At the very highest recursion level you allocate a vector of 8 elements. After that you visit both left and right subranges of length 4 elements each. That's 8 elements in vector(s) more. You continue the same argument until you reach the bottom recursion level. Since each level allocates \$N = 8\$ worth memory, and there is \$\Theta(\log N)\$ levels total, you get \$\Theta(N \log N)\$.