merge sort

[Sarahger9]

I am trying to generate a random vector of integers and sort them using merge sort.
I am having trouble with the code. It is long, but I would appreciate if someone could take a look at it and see if the can help me, I've been working on it for days and am completely stuck.
When I run the program, it just stops at the point where I call the mergesort. I believe the problem may be in the merge split, because when I cout the values for low, high, and half there, I get 0 1 and 1, and this never changes. Thanks for the help.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> merge(vector<int> list1, vector<int> list2){
    vector<int> result;
    int int1=0;
    int int2=0;
    cout << "merging lists" << endl;
    while(int1 < list1.size() || int2 < list2.size())
    {
        if (int1 < list1.size() && int2< list2.size())
        {
            if (list1[int1] < list2[int2])
                    result.push_back(list1[int1++]);
                else 
                    result.push_back(list2[int2++]);
            }
            else{
                while(int1 < list1.size())
                    result.push_back(list1[int1++]);
                while(int2 < list2.size())
                    result.push_back(list2[int2++]);
            }
        }
        return result;
    }
 
vector <int> merge_split(vector<int> list, int low, int high){
    cout << "performing merge split" << endl;
    int half = ((high +1) - low)/2;
    cout << low << "  " << high << "  " << half << endl;
    if (high = low){
        vector<int> res;
        res.push_back(list[low]);
        return res;
    }
    else if (high - low == 1){
        vector <int> res;
        if(list[low] < list[high]){
            res.push_back(list[low]);
            res.push_back(list[high]);
        }
        else {
            res.push_back(list[high]);
            res.push_back(list[low]);
        }
    }
        vector<int> list1 = merge_split(list, low, low + half);
        vector<int> list2 = merge_split(list, low + half + 1, high);
        return merge(list1, list2);
}
 
void merge_sort(vector<int> &list){
    cout << "performing merge sort" << endl;
    int low = 0;
    int high = list.size() - 1;
    list = merge_split(list, low, high);
    return;
}
 
int main(){
    int i;
    vector <int> list;
    for (i = 0; i < 20; i++){
        list.push_back(rand());
    }
    int size = 20;
    cout << "Before" << endl;
    for (i = 0; i < size; i++)
        cout << list[i] << "  ";
    cout << endl;
    merge_sort(list);
    cout << "merge sort, after" << endl;
    cout << "After";
    for(i = 0; i < size; i++){
        cout << list[i] << "  ";
    }
    cout << endl;
    return 0;
}

[mschenkelberg]

if ( high = low )
{
....
}

The first thing you are doing in merge_split is storing the value of low in high which will then evaluate to false every time... bad!

I'm surprised you didn't get a compiler warning for that code. What compiler are you using?

[Sarahger9]

I'm using visual basic. It compiled, but wouldn't complete the code, it would just break off.

But I am having trouble with what you are saying, how should I go about declaring the low and high values?

[Sarahger9]

Oh, I see what you mean now, thank you very much

[Sarahger9]

Unfortunately, that was not the only problem though. It still doesnt work.

[mschenkelberg]

Well, you definitely need to rethink your merge( list, list ) logic. That code is definitely wrong.

Max