# I'm having trouble with my Merge Sort - tried it a couple different ways and this sma

• February 25th, 2013, 11:15 PM
ApacheOmega
I'm having trouble with my Merge Sort - tried it a couple different ways and this sma
I have created a program that first sorts a series of numbers that are input dynamically then an option is given to either use a sequential search or a Binary search. my sequential search works fine but the merge sort coupled with the binary search has a small bug that I just can't seem to figure how to eliminate. I first used my own merge sort but it was really in efficient so a I took a more effient example and incorporated it in my program but I cant seem to get rid of this bug I'm dealing with. and it seems to be causing a futher problem with the Binary seach. I have entered the ful code (sorry about the length) and I'm hoping anybody can lead me in the right direction towards fixing this.

here's my code

Code:

```#include <iostream> #include <cmath> using namespace std; const int N = 10; // A simple print function void print(int *A) {     for ( int i = 0; i < N; i++ )         cout << A[i] << " ";     cout << endl; } void merge(int* A, int p, int r) {     int mid = floor((p + r) / 2);     int i1 = 0;     int i2 = p;     int i3 = mid + 1;     // Temp array //////I tried this two different ways but nothing seems to work         //int temp [r-p+1];     int temp = new int[r-p+1];     // Merge in sorted form the 2 arrays     while ( i2 <= mid && i3 <= r )         if ( A[i2] < A[i3] )             temp[i1++] = A[i2++];         else             temp[i1++] = A[i3++];     // Merge the remaining elements in left array     while ( i2 <= mid )         temp[i1++] = A[i2++];     // Merge the remaining elements in right array     while ( i3 <= r )         temp[i1++] = A[i3++];     // Move from temp array to master array     for ( int i = p; i <= r; i++ )         A[i] = temp[i-p]; } void merge_sort(int* A, int p, int r) {     if ( p < r )     {         int mid = floor((p + r) / 2);         merge_sort(A, p, mid);         merge_sort(A, mid + 1, r);         merge(A, p, r);     } } int sSearch(int A[], int N, int V) {         for(int i=1;i<=N; i=i+1)         {                 if (V==A[i]){                         cout<<"Data found at position:  "<<i<<endl;                 return i;                 }         } } int bSearch(int A[], int p, int r, int V) {         if (p<r)                 {                 int mid =(p+r)/2;                         if(V==A[mid])                                 return mid;                                         else if (V<A[mid])                                                 return bSearch(A, p, mid-1,V);                                                         else                                                 return bSearch(A, mid+1, r, V);                                         }                                 if (V==A[p])                 return p;         else return-1; } int main(){                         int N, i, V, option, p, r;                 cout<<"Please enter the size of Array "<<endl;                                 cin>>N;                                         int* A ;                                         A= new int[N];                                         cout<<"Please enter each numerical value "<<endl;                                                 for(i=1;i<=N;i++)                                                         {                                                         cin>>A[i];                                                                                                                 }                                                 merge_sort(A, 0, 9);                                                 cout<<A<<endl;                 cout<<"Choose the desired task to perform"<<endl;                 cout<<"For Sequence Search select: (option 1)"<<endl;                 cout<<"For Binary Search select: (option 2)"<<endl;                 cin>>option;                 cout<<endl;                         if(option ==1)                                 {                                         cout<<"Please enter the digit you are searching for "<<endl;                                                 cin>>V;                                                         cout<<endl;                                                         i=sSearch(A, N, V);                                                         if (A[i]!=V){                                                 cout<<"Value Not Found "<<endl;                                         }                                 }                                         else        if (option ==2)                                                 {                                                         cout<<"Please enter the digit you are searching for "<<endl;                                                                 cin>>V;                                                                         cout<<endl;                                                                                 bSearch(A, p, r, V);                                                                         if (A[i]!=V){                                                                 cout<<"Value Not Found "<<endl;                                                         }                                                 } system ("PAUSE"); return 0; }```
Can anybody please tell me what I'm pulling out the little hair I got over
Thank You!!!
• February 25th, 2013, 11:16 PM
ApacheOmega
Re: I'm having trouble with my Merge Sort - tried it a couple different ways and this
i think i might have accidentally posted twice sorry!!!
• February 26th, 2013, 01:19 AM
josh26757
Re: I'm having trouble with my Merge Sort - tried it a couple different ways and this
Here is an example I found here:

I had to change it around a bit to get it to compile, but it is now a working example.

Code:

```#include <iostream> #include <cmath> using namespace std; const int INPUT_SIZE = 10; // A simple print function void print(int *input) {     for ( int i = 0; i < INPUT_SIZE; i++ )         cout << input[i] << " ";     cout << endl; } void merge(int* input, int p, int r) {     int mid = (p + r) / 2;     int i1 = 0;     int i2 = p;     int i3 = mid + 1;     // Temp array     int temp[INPUT_SIZE];     // Merge in sorted form the 2 arrays     while ( i2 <= mid && i3 <= r )         if ( input[i2] < input[i3] )             temp[i1++] = input[i2++];         else             temp[i1++] = input[i3++];     // Merge the remaining elements in left array     while ( i2 <= mid )         temp[i1++] = input[i2++];     // Merge the remaining elements in right array     while ( i3 <= r )         temp[i1++] = input[i3++];     // Move from temp array to master array     for ( int i = p; i <= r; i++ )         input[i] = temp[i-p]; } void merge_sort(int* input, int p, int r) {     if ( p < r )     {         int mid = ((p + r) / 2);         merge_sort(input, p, mid);         merge_sort(input, mid + 1, r);         merge(input, p, r);     } } int main() {     int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};     cout << "Input: ";     print(input);     merge_sort(input, 0, 9);     cout << "Output: ";     print(input);         system("PAUSE");     return 0; }```

Good Luck!
• February 26th, 2013, 01:48 PM
2kaud
Re: I'm having trouble with my Merge Sort - tried it a couple different ways and this
Quote:

I had to change it around a bit to get it to compile
There are also problems with other programs from the same site - some with serious buffer overrun security issues. I don't know what version of c++ is used, but it's not ANSI c++. One of the less serious problems is the expectation of creating a standard array (eg of int) with the number of elements computed at run time!