# Merge and MergeSort Algorithms Problem

Page 1 of 1

## 2 Replies - 681 Views - Last Post: 04 October 2012 - 10:03 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294201&amp;s=1a8c19255c1457ed66b3402209cf3bec&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 jamesa8

• New D.I.C Head

Reputation: 0
• Posts: 6
• Joined: 03-October 12

# Merge and MergeSort Algorithms Problem

Posted 03 October 2012 - 11:28 PM

```
/**
* MERGE SORT Class to implement a sorting algorithm
* ====================================================================
*/

#include <iostream>

using namespace std;

void Merge(int begin, int end,  int Array[], int mid) {
// make comparitives and create subarray
// int* ArrayTemp = new int[end];
// creates a temp array
int ArrayTemp[end] ;
int beg = begin;                       // takes sub array and has the placehold begining
int beg2= mid+1;                   // start of second subarray
int last = mid;                         // end of the first subarray
int last2 = end;                     // end of the second subarray
int index = beg;
cout<< "variables in merge initialized" ;
//do the following as long as the array isn't empty or has one number
for ( ; (beg <= last) && (beg2 <=last2 ); index++) {
cout << "I am going through the first for loop. " ;
if (Array[beg] < Array[beg2]){                      // if the subarray1 first is less than subarray2
ArrayTemp[index] = Array[beg] ;          //temparray at index value will be subarray1
beg++;
cout<<" I am the first if loop" ;
//increase the value of the arraysubset1 so next comp is beg[2] vs beg2[1]
}

//if the above is not true then put subarray2 value into the index of the temp array.
else{
cout<< "I am the else statement" ;
ArrayTemp[index] = Array[beg2];
beg2++ ;

}
}

//the following 2 while loops basically say if one of the subarrays is empty add the rest of
//the other array into the temp array.
cout<<"for loop has ended" ;
while (beg <=last ) {
cout<< "i am the first while loop " ;
ArrayTemp[index] = Array[beg];
index++;
beg++;
}

while (beg2 <= last2 ) {
ArrayTemp[index] = Array[beg2];
index++;
beg2++;
cout<< "I am the second output statement" ;
}

//make index equal to the origin of the array

// make the array permanent. Place all values of the temp array into the actual array.
cout << "before transfer " <<endl;
for (int i = 0; i < last ;i++ ){
Array[i] = ArrayTemp[i];
}

}

void MergeSort (int begin , int end,  int Array[]) {
//check and see if the beginning of the array is less than the end of the array
//if so then find the middle and recursively call the function until it divies up everything.
cout << "begin = " << begin <<   "     end  = " << end<< endl;

if ( begin >= end ) {
return;
cout << "bad value " ;
}

else {
int mid = (begin+end)/2 ;
cout<< " mid worked" ;
MergeSort( begin, mid, Array);
cout<< "merge 1 worked" ;           //recursive call keeps breaking down array
MergeSort(mid+1, end, Array);
cout<<"merge2 worked" ;             // recursive call keeps breaking down array.
Merge ( begin, end, Array, mid);
cout<< "merge 3 worked" ;         // merges array

cout << "i am done tranfering the temporary array to the main array" ;

}
}

```

Hello. I have this merge sort code which I have been attempting to figure out. At first it gave me a segmentation fault but now the code is throwing out just a whole bunch of random numbers and a lot of 0's which are not even sorted properly. I have tried debugging it by placing the above cout statements, i have looked at other example code, and I have adjusted end, I have switched my static arrays to dynamic ones, and adjusted my index values to see if I was affecting those all. None of it seems to be helping. Are there any ideas or adjustments that would make it run?

Is This A Good Question/Topic? 0

## Replies To: Merge and MergeSort Algorithms Problem

### #2 Skydiver

• Code herder

Reputation: 4823
• Posts: 15,950
• Joined: 05-May 12

## Re: Merge and MergeSort Algorithms Problem

Posted 03 October 2012 - 11:48 PM

I need to look closely at the rest of the code, but at first glance, your for loop on lines 66-68 only copies half of the array because last == mid based on line 20.

### #3 jamesa8

• New D.I.C Head

Reputation: 0
• Posts: 6
• Joined: 03-October 12

## Re: Merge and MergeSort Algorithms Problem

Posted 04 October 2012 - 10:03 AM

Hi. Thanks so much for pointing that out. I adjusted the code and ran some debugging cout statements. From what I am seeing there is a part of the code where it is rewriting the array values. Like when I put in the values 0 1 2 3 4 5 6 7 8 9 as an array input the output resulted in 0 13 32597 6299776 0 452795280 452795280 452795280. Any thoughts?