Merge sort not working

[Andrei123f]

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

#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]

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]

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

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:

// 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:

    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.