MergeSort. Implementation with Iterators

Question

I need to implement the algorithm of mergesort with following interface:

template <typename T, typename Comp>
void mergesort(T begin, T end, Comp comp);

where begin and end - iterators for elements of some container of type T, comp - is function of comparing elements, which are stored in container. And

template <typename T, typename Comp>
void merge(T beginLeft, T endLeft, T beginRight, T endRight,
                T beginResult, Comp comp);

is function of merging of two sorted containers (beginLeft and endLeft - iterators of the first container, beginRight and endRight - of the second) and result should be iterator to the begining of new merged container beginResult.

It should be look like this.

I've wrote recursive function for merge sort, which calls the procedure of merging.

template <typename T, typename Comp>
void mergesort(T begin, T end, Comp comp)
{
    if (begin == std::prev(end))
    {
        return;
    }    

    T middle = begin + std::distance(begin, end) / 2;

    mergesort<T, Comp>(begin, middle, comp);
    mergesort<T, Comp>(middle, end, comp);

    merge<T, Comp>(begin, middle, middle, end, begin, comp);
}

template <typename T, typename Comp>
void merge(T beginLeft, T endLeft, T beginRight, T endRight,
                T beginResult, Comp comp)
{
    while (beginLeft != endLeft && beginRight != endRight)
    {
        if (comp(*beginLeft, *beginRight))
        {
            *beginResult = *beginLeft;
            ++beginResult;
            ++beginLeft;
        }
        else
        {
            *beginResult = *beginRight;
            ++beginResult;
            ++beginRight;
        }
    }

    while (beginLeft != endLeft)
    {
        *beginResult = *beginLeft;
        ++beginResult;
        ++beginLeft;
    } 
    while (beginRight != endRight)
    {
        *beginResult = *beginRight;
        ++beginResult;
        ++beginRight;
    } 
}

Function merge works correctly, but I don't quite understand, how mergesort should work. What argument should I pass to

merge<T, Comp>(begin, middle, middle, end, /?...?/, comp);

If I pass just begin there, than the result of sorting is not correct. Or should I pass there some temporary container. But how can I create it, if I have only type of iterator and don't know the type of elements?

I will be grateful for your help. Thank you!

--ADDED---

Example of merging:

vector<int> vec1;
vector<int> vec2;
vector<int> vec3(6);
vec1.push_back(1);
vec1.push_back(3);
vec1.push_back(5);
vec2.push_back(2);
vec2.push_back(4);
vec2.push_back(6);
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin(), std::less<int>()); 

for (int i = 0; i < vec3.size(); ++i)
{
    std::cout << vec3[i] << std::endl;
}

Output is: 1 2 3 4 5 6

how dyou know that *merge* works correctly if you don't even know how to call it? — Karoly Horvath, Dec 23 '13 at 10:27
What you require is an in-place merge sort. This is not easy to implement as this link states: http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm — Abhishek Bansal, Dec 23 '13 at 10:42

Shahbaz · Answer 1 · 2013-12-23T10:43:51.043

For sure you can't use begin to store the result. You are still reading from begin and merging, so by writing to it you would be overwriting data that are possibly still not read.

You would need temporary memory to write the result to, and then copy back over the original. The memory could be of any type, so long as you can get an iterator over it. Say a std::vector.

There's a fundamental problem though. You have the type of all five iterators in merge as T, but at least the type of beginResult should be of a possibly different iterator. Otherwise, you can't know, as you have observed, what temporary container to use.

As you have linked yourself, the template of std::merge has different iterator types for the left, right and result iterators.

Note: to allocate temporary memory, you need to know the type of elements that T is an iterator of. This is simply done by T::value_type. See here.

Didn't, even nearly, address the actual question. – Francisco Aguilera Apr 27 '15 at 07:19 — Francisco Aguilera, Apr 27 '15 at 07:19

score 0 · Answer 2 · answered Dec 26 '13 at 13:54

Something like this should work:

template<class BiDirIt, class Compare = std::less<typename std::iterator_traits<BiDirIt>::value_type>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare())
{
        auto const N = std::distance(first, last);
        if (N < 2) return;
        auto middle = first + N / 2;
        merge_sort(first, middle, cmp);
        merge_sort(middle, last, cmp);
        std::inplace_merge(first, middle, last, cmp);
}

Francisco Aguilera · Answer 3 · 2015-04-27T07:34:10.370

0

You can create your vector as such:

std::vector<std::iterator_traits<T>::value_type> result;

in a helper function, then call your sort routine:

merge_sort(first, last, result.begin());

Then once your function comes back with results, you can copy the results to the vector denoted by the user-provided iterators.

edited Apr 27 '15 at 07:34

answered Apr 27 '15 at 07:18

Francisco Aguilera

3,099
6
31
57

MergeSort. Implementation with Iterators

3 Answers3