Merge sort not working

Andrei123f (4)
I have been trying to understand why it does not work for 3-4 hours straight and I still do not get it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
#include<iostream>

using namespace std;
int v[100],b[100],n,i;


void showAr(int end, int start, int v[100])
{
    for(i=end;i<=start;i++)
        cout<<v[i];
    cout<<endl;
}

void sortm(int end, int start,int v[100])
{
    int aux;



    if(v[start]>v[end])
    {
        aux=v[start];
        v[start]=v[end];
        v[end]=aux;
    }
}

void mergeAr(int start, int end, int m, int v[100])
{
    int b[100],k=1,i=start,j=m+1;

    while(i<m&&j<end)
                    if(v[i]>v[j])
                                b[k++]=v[j++];
                    else
                        b[k++]=v[i++];

    while(i<m)
        b[k++]=v[i++];
    while(j<end)
        b[k++]=v[j++];

    for(i=1;i<=end;i++)
        v[i]=b[i];



}




void merge_sort(int start, int end, int v[100])
{
    int m;

    if((end-start)<=1)
        sortm(end, start,v);
    else
    {



    m=(start+end)/2;

    merge_sort(start,m,v);
    merge_sort(m+1,end,v);

    mergeAr(start,end,m,v);

    }
}

int main()
{
    cout<<"n= "; cin>>n;

    for(i=1;i<=n;i++)
        cin>>v[i];

   // for(i=1;i<=n;i++)
       // cout<<v[i]<<" ";

        merge_sort(1,n,v);

         for(i=1;i<=n;i++)
        cout<<v[i]<<" ";


}
Grunalin (27)
First thing that stands out is....

for(i=end;i<=start;i++)

would it not be other way around

for (i = start; i < end; I++)
dhayden (5798)
It's best to interpret a range X-Y to mean "values starting at X and running up to but not including Y." The mathematical notation is [X,Y). This is the way the standard library does it. My comments below modify your code to work that way.

showAr()'s args are backwards. I'd change it to 
1
2
3
4
5
6
7
 
void
showAr(int start, int end, int v[100])
{
    for (i = start; i<end; ++i)
        cout << v[i] << ' ';
    cout << endl;
}

Notice that this interprets the range as NOT including end.

Remove sortm(). YOu don't need it.
Line 30: initialize k=0. You might as well use all of array b.
also initialize j=m, since j goes through the second range which we've defined as starting at m.
mergeAr(). Let's start by defining exactly what it should do:
1
2
3
4
5
 
// Given a vector v where:
//   the numbers in [start,j) are sorted, and 
//   the numbers in [j,end) are sorted, and 
//   all numbers in [start,j) are less than the numbers in [j,end),
//  Sort the range [start, end).


Everything else looks good until line 43 where you put the values back. That loop should be:
1
2
 
    for (i = start; i < end; i++)  // i goes [start,end)
        v[i] = b[i-start];  // copy from the right place in b.

Now you can see why it's best to start k at 0. If it started at 1, you'd have to add 1 to the index for b here. Yuck.

Line 67. Now that we're crystal clear on our ranges, this should obviously be
merge_sort(m, end, v)

Line 84. Since you put the values into v[1]...v[n] instead of v[0]...v[n-1], this should be
merge_sort(1, n+1, v);

When I make these changes it works for me.
Topic archived. No new replies allowed.