2
\$\begingroup\$

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.)

\$\endgroup\$
4
\$\begingroup\$

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)\$.

\$\endgroup\$
  • \$\begingroup\$ "Swapping roles at each level of recursion" - this can be implemented with a boolean direction parameter that toggles with each level of recursion, or as a pair or mutually recursive functions. One function (or even level of recursion) sorts from vec to vec, the other from vec to result. Vec to vec merge sort calls vec to result merge sort twice, then merges the two parts of result back to vec. Vec to result merge sort does the opposite, except if vec.size() == 1, it copies one element from vec to result. \$\endgroup\$ – rcgldr Sep 16 '16 at 23:30
  • \$\begingroup\$ @coderodde - Hey, this is super helpful! Thanks! I'm taking some time to review this. However, I have a question. If I count all of "std::vector<T> result(size);..." When exiting the merge function in each successive stack call, the local memory is deleted, is it not? Hence, I thought the worst case would be O(N) (theta(N) if I had to give a more accurate bound). Could you please elaborate on how it would instead be theta(NlogN)? I might be having a brain freeze. \$\endgroup\$ – Raaj Sep 17 '16 at 2:13
  • \$\begingroup\$ @Raaj I added explanation to the \$\Theta(N \log N)\$ memory argument. \$\endgroup\$ – coderodde Sep 17 '16 at 4:39
  • \$\begingroup\$ @coderodde - The levels of recursion do not occur at the same time, and the temp vectors are released after each instance of merge returns. So at the bottom most level along any path, what's been allocated is a vector of size 8, then size 4, then size 2. As N becomes very large, the amount of space allocated at the bottom level approaches 2N. Still, compared to doing a one time allocation at the start, the recursive allocations can fragment memory and take up twice the space. \$\endgroup\$ – rcgldr Sep 17 '16 at 8:42
  • \$\begingroup\$ @rcgldr Yes, I understand that at any given instant no more than \$2N\$ elements are being actually allocated. My point was that if you sum all the memory allocated by OP's implementation, you will obtain (roughly) \$N \log N\$ worth memory. \$\endgroup\$ – coderodde Sep 17 '16 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.