C++ Merge Sort using iterators

Question

Currently, I am trying to create a simple C++ Merge Sort Program.

using namespace std;

using Iterator = std::vector::iterator;
using CIterator = std::vector::const_iterator;
std::vector merge(CIterator left_begin, CIterator left_end, CIterator right_begin, CIterator right_end) {
    std::vector result;
    
    CIterator left = left_begin;
    CIterator right = right_begin;
    
    while (left != left_end && right != right_end) {
        if (*left <= *right) {
            result.push_back(*left);
            left++;
        } else {
            result.push_back(*right);
            right++;
        }
    }
    
    while (left != left_end) {
        result.push_back(*left);
        left++;
    }
    
    while (right != right_end) {
        result.push_back(*right);
        right++;
    }
    
    return result;
}

I created a merge function that basically connects two sorted vectors into one and returns it (I am bound to use the following return type of the function merge). Then Trying to write the driver function merge sort I have the following code, that I think works correctly

void merge_sort(Iterator begin, Iterator end) {
    auto difference = distance(begin, end);
    
    if (difference <= 1) {
        return;
    }
    
    Iterator middle = begin;
    advance(middle, difference / 2);
    
    merge_sort(begin, middle);
    merge_sort(middle, end);
    
    vector result = merge(begin, middle, middle, end);
    // But what to put here?
}

At the place of the comment mark, I don't understand what to write in order to move the sorted array a step up in the recursion. I tried

    begin = result.begin();
    end = result.end();

but this obviously doesnt work

user_565635 · Answer

The problem is that the type signature for merge_sort assumes an in-place algorithm:

void merge_sort(Iterator begin, Iterator end);

But your merge procedure isn't in-place but returns a merged copy of the arrays. You either need to change merge to be in-place, or you need to change merge_sort to return the sorted array. The latter solution (easier but less efficient) would be like this:

std::vector merge_sort(Iterator begin, Iterator end) {
    auto difference = distance(begin, end);
    
    if (difference <= 1) {
        return;
    }
    
    Iterator middle = begin;
    advance(middle, difference / 2);
    
    std::vector left = merge_sort(begin, middle);
    std::vector right = merge_sort(middle, end);
    return merge(left.begin(), left.end(), right.begin(), right.end());
}

user_3282056 · Answer

An optimized top down merge sort that does a one time allocation of a second vector, then uses a pair of mutually recursive functions (...AtoA, ...AtoB) to alternate the direction of merge based on level of recursion. (I left out the prototypes).

void MergeSort(     typename std::vector::iterator &ab,
                    typename std::vector::iterator &ae)
{
    size_t sz = ae - ab;
    if (sz < 2)
        return;
    std::vector vb(sz);           // temp vector
    std::vector::iterator bb = vb.begin();
    std::vector::iterator be = vb.end();
    MergeSortAtoA(ab, ae, bb, be);
}

void MergeSortAtoA( typename std::vector::iterator &ab,
                    typename std::vector::iterator &ae,
                    typename std::vector::iterator &bb,
                    typename std::vector::iterator &be)
{
    size_t sz = ae - ab;
    if(sz < 2)                              // if 1 element return
        return;
    std::vector::iterator am = ab+(sz/2);
    std::vector::iterator bm = bb+(sz/2);
    MergeSortAtoB(ab, am, bb, bm);
    MergeSortAtoB(am, ae, bm, be);
    Merge(bb, bm, be, ab);
}

void MergeSortAtoB( typename std::vector::iterator &ab,
                    typename std::vector::iterator &ae,
                    typename std::vector::iterator &bb,
                    typename std::vector::iterator &be)
{
    size_t sz = ae - ab;
    if(sz < 2){                             // if 1 element, copy it
        *bb = *ab;
        return;
    }
    std::vector::iterator am = ab+(sz/2);
    std::vector::iterator bm = bb+(sz/2);
    MergeSortAtoA(ab, am, bb, bm);
    MergeSortAtoA(am, ae, bm, be);
    Merge(ab, am, ae, bb);
}

void Merge(         typename std::vector::iterator &ab,
                    typename std::vector::iterator &am,
                    typename std::vector::iterator &ae,
                    typename std::vector::iterator &bb)
{
std::vector::iterator mb = ab;    // left  run iterator
std::vector::iterator mm = am;    // right run iterator
std::vector::iterator bi = bb;    // merge run iterator

    while(1){                               // merge data
        if(*mb <= *mm){                     // if mb <= mm
            *bi++ = *mb++;                  //   copy mb
            if(mb < am)                     //   if not end left run
                continue;                   //     continue (back to while)
            while(mm < ae)                  //   else copy rest of right run
                *bi++ = *mm++;
            break;                          //     and return
        } else {                            // else mb > mm
            *bi++ = *mm++;                  //   copy mm
            if(mm < ae)                     //   if not end of right run
                continue;                   //     continue (back to while)
            while(mb < am)                  //   else copy rest of left run
                *bi++ = *mb++;
            break;                          //     and return
        }
    }
}

C++ Merge Sort using iterators

2 Answers