Having issues which Mergesort's compare and ordering part (c++)

Question

I have read and understood how Mergesort works (as a text) and now I'm trying to code it. I have finished the part where you divide the data (I use vectors) until it has each size of 1. Now I have written code for another required part in Mergesort, I don't know how to call it but I just call it "compare and ordering part".

You have 2 vectors and this part is supposed to compare the very first elements, take the smaller element, then remove the chosen element and put it inside a new vector. Doing that untill both vectors have size 0.

I'm sorry for the long code but I really don't see why the very last element is ignored by the code? : / I have added some comments so maybe it is easier to follow what I tried to do.

I tried as input:

vector<int> v1 = {1,4,5,9};
vector<int> v2 = {2,3,6,7,8};

Output:

1 2 3 4 5 6 7 8 0

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (left.size() > 0 && right.size() > 0) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i) = left.at(0);      // putting the smaller element into the new vector
            left.erase(left.begin());       // removing this smaller element from the (old) vector
        }
        else if (right.at(0) <= left.at(0)) {
            sorted.at(i) = right.at(0);     // see comment above
            right.erase(right.begin());     // see comment above
        }
        else if (left.size() <= 0 && right.size() > 0) {    // if left vector has no elements, then take all elements of the right vector and put them into the new vector
            while (right.size() > 0) {
                sorted.at(i) = right.at(0);
                right.erase(right.begin());
            }
        }
        else if (right.size() <= 0 && left.size() > 0) {    // the same just for the right vector
            while (left.size() > 0) {
                sorted.at(i) = left.at(0);
                left.erase(left.begin());
            }
        }
        i++;
    }
    return sorted;
}

Related: [Implementing sorts](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — Caleth, Mar 18 '19 at 09:21

score 2 · Accepted Answer · answered Mar 17 '19 at 22:38

The check of whether one of the arrays has exhausted and other array has remaining elements should be outside the main while loop. So, try to put the below two checks outside.

else if (left.size() <= 0 && right.size() > 0)    

else if (right.size() <= 0 && left.size() > 0)

Think of what will happen when one array has (1) and other (2,3), On adding 1 to the sorted vector, the while(left.size() > 0 && right.size() > 0) condition is false and the loop breaks. So the other elements are ignored.

score 1 · Answer 2 · answered Mar 18 '19 at 07:02

don't know how to call [the] "compare and ordering part"

Conventionally: merge

sorry for the long code

use a

first = *left <= *right ? left : right

and manipulate that, avoiding code replication.

don't see why the very last element is ignored by the code?

left.at(0) <= right.at(0)

and

right.at(0) <= left.at(0)

cover all possible comparison results (equality twice): no further else will get evaluated.
Moving "the move parts" to follow "the proper merge" as suggested by Msk, note that the preliminary checks are dispensable - just use "the move loops".

There is a lot to say about your code (starting with commentation) - see code reviews of C++ merge implementations for ideas.
If you want code you are in control of reviewed at CR@SE, be sure to be on topic and write a Good Question.

score 1 · Answer 3 · answered Mar 18 '19 at 07:07

The code could be simplified:

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (1) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i++) = left.at(0);
            left.erase(left.begin());
            if(left.size == 0){
                do{
                    sorted.at(i++) = right.at(0);
                    right.erase(right.begin());
                }while(right.size != 0);
                return;
            }
        } else {
            sorted.at(i++) = right.at(0);
            right.erase(right.begin());
            if(right.size == 0){
                do{
                    sorted.at(i++) = left.at(0);
                    left.erase(left.begin());
                }while(left.size != 0);
                return;
            }
        }
    }
    return sorted;
}

rather than erasing elements of vectors, indexing could be used instead:

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    int ll = 0;
    int rr = 0;
    while (1) {
        if (left[ll] <= right[rr]) {
            sorted[i++] = left[ll++];
            if(ll == left.size){
                do{
                    sorted[i++] = right[rr++];
                }while(rr != right.size);
                break;
            }
        } else {
            sorted[i++] = right[rr++];
            if(rr == right.size){
                do{
                    sorted[i++] = left[ll++];
                }while(ll != left.size);
                break;
            }
        }
    }
    return sorted;
}

Having issues which Mergesort's compare and ordering part (c++)

3 Answers3