Implementation of Merge Sort in C++

Question

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<typename T> void merge(std::vector<T> &vec, int left, int mid, int right )
{
    int i=left;
    int j=mid+1;
    int k=0;
    int size = (right - left) +1;
    std::vector<T> result(size);

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

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

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

    if (left<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<int> 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.)

Answer 1

Instability

while(i <= mid && j <= right)  result[k++] = (vec[i] < 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 <= mid && j <= right)  result[k++] = (vec[i] <= vec[j])? vec[i++] : vec[j++];

or even:

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

Misc 1

while(i <= mid)                result[k++] = vec[i++];
while(j <= 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<typename RandIt1, typename RandIt2>
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 < 2)
    {
        return;
    }

    auto left_subrange_length = range_length >> 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<typename RandIt>
void mergeSort(RandIt begin, RandIt end)
{
    auto range_length = std::distance(begin, end);

    if (range_length < 2)
    {
        return;
    }

    using value_type = typename std::iterator_traits<RandIt>::value_type;
    std::vector<value_type> aux(begin, end);
    mergeSort(aux.begin(), aux.end(), begin, end);
}

template<typename T>
void mergeSort(std::vector<T>& 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<T> 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 < 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)\$.