By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,027 Members | 1,088 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,027 IT Pros & Developers. It's quick & easy.

merge sort

P: 14
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.

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int> merge(vector<int> list1, vector<int> list2){
  6.     vector<int> result;
  7.     int int1=0;
  8.     int int2=0;
  9.     cout << "merging lists" << endl;
  10.     while(int1 < list1.size() || int2 < list2.size())
  11.     {
  12.         if (int1 < list1.size() && int2< list2.size())
  13.         {
  14.             if (list1[int1] < list2[int2])
  15.                     result.push_back(list1[int1++]);
  16.                 else 
  17.                     result.push_back(list2[int2++]);
  18.             }
  19.             else{
  20.                 while(int1 < list1.size())
  21.                     result.push_back(list1[int1++]);
  22.                 while(int2 < list2.size())
  23.                     result.push_back(list2[int2++]);
  24.             }
  25.         }
  26.         return result;
  27.     }
  28.  
  29. vector <int> merge_split(vector<int> list, int low, int high){
  30.     cout << "performing merge split" << endl;
  31.     int half = ((high +1) - low)/2;
  32.     cout << low << "  " << high << "  " << half << endl;
  33.     if (high = low){
  34.         vector<int> res;
  35.         res.push_back(list[low]);
  36.         return res;
  37.     }
  38.     else if (high - low == 1){
  39.         vector <int> res;
  40.         if(list[low] < list[high]){
  41.             res.push_back(list[low]);
  42.             res.push_back(list[high]);
  43.         }
  44.         else {
  45.             res.push_back(list[high]);
  46.             res.push_back(list[low]);
  47.         }
  48.     }
  49.         vector<int> list1 = merge_split(list, low, low + half);
  50.         vector<int> list2 = merge_split(list, low + half + 1, high);
  51.         return merge(list1, list2);
  52. }
  53.  
  54. void merge_sort(vector<int> &list){
  55.     cout << "performing merge sort" << endl;
  56.     int low = 0;
  57.     int high = list.size() - 1;
  58.     list = merge_split(list, low, high);
  59.     return;
  60. }
  61.  
  62. int main(){
  63.     int i;
  64.     vector <int> list;
  65.     for (i = 0; i < 20; i++){
  66.         list.push_back(rand());
  67.     }
  68.     int size = 20;
  69.     cout << "Before" << endl;
  70.     for (i = 0; i < size; i++)
  71.         cout << list[i] << "  ";
  72.     cout << endl;
  73.     merge_sort(list);
  74.     cout << "merge sort, after" << endl;
  75.     cout << "After";
  76.     for(i = 0; i < size; i++){
  77.         cout << list[i] << "  ";
  78.     }
  79.     cout << endl;
  80.     return 0;
  81. }
Dec 3 '07 #1
Share this Question
Share on Google+
5 Replies


mschenkelberg
P: 44
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?
Dec 3 '07 #2

P: 14
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?
Dec 3 '07 #3

P: 14
Oh, I see what you mean now, thank you very much
Dec 3 '07 #4

P: 14
Unfortunately, that was not the only problem though. It still doesnt work.
Dec 3 '07 #5

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

Max
Dec 3 '07 #6

Post your reply

Sign in to post your reply or Sign up for a free account.