Merge Sort Algorithm?

Question

I can't figure out what is wrong with my MergeSort function. This is my code:

void Merge(int* A, int p, int q, int r)
{
    int B[100], i = 0, j = 0, k = 0;

    i = p;
    k = p;
    j = q + 1;

    while (i <= q && j <= r)
    {
        if (A[i] <= A[j])
        {
            B[k] = A[i];
            k++;
            i++;
        }

        else
        {
            B[k] = A[j];
            k++;
            j++;
        }
    }

    while (i <= q)
    {
        B[k] = A[i];
        k++;
        i++;
    }

    while (j <= r)
    {
        B[k] = A[j];
        k++;
        j++;
    }

    for (i = p; i < r; i++)
    {
        A[i] = B[i];
    }
}


void MergeSort(int A[], int p, int r)
{
    int q;

    if (p < r)
    {
        q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}


int main(void)
{
    int N[10];

    N[0] = 4;
    N[1] = 5;
    N[2] = 8;
    N[3] = 12;
    N[4] = 7;
    N[5] = 3;
    N[6] = 23;
    N[7] = 1;
    N[8] = 90;
    N[9] = 26;

    MergeSort(N, 0, 9);

    for (int i = 0; i < 10; i++)
    {
        cout << N[i] << endl;
    }
}

The output of program is: 1, 3, 1, 4, 5, 7, 7, 7, 26, 26, which is obviously wrong. However I just don't see what is wrong in code, to me everthing looks good. I googled some C++ codes of MargeSort and try to debug it but i can't find mistake. Anyone see it?

Answer 1

//you have just one err,in last for you missed = :

//err: for(i = p; i < r; i++)

//correct: for(i = p; i <= r; i++)

#include <iostream>
using namespace std;
void Merge(int* A, int p, int q, int r)
{
    int B[100], i = 0, j = 0, k = 0;
    i = p;
    k = p;
    j = q + 1;
    while (i <= q && j <= r)
    {
         if (A[i] <= A[j])
         {
            B[k] = A[i];
            k++;
            i++;
        }
        else
        {
            B[k] = A[j];
            k++;
            j++;
        }
    }

    while (i <= q)
    {
        B[k] = A[i];
        k++;
        i++;
    }

    while (j <= r)
    {
        B[k] = A[j];
        k++;
        j++;
    }

    for (i = p; i <= r; i++)
    {
        A[i] = B[i];
    }
}

void MergeSort(int A[], int p, int r)
{
    int q;

    if (p < r)
    {
        q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}


int main(void)
{
    int A[10]={9,8,7,6,5,4,3,2,1,0};
    MergeSort(A,0,9);
    for (int i = 0; i<10; i++)
    {
        cout<<A[i]<<",";
    }
}

//this is cleaned version of your code:

#include <iostream>
using namespace std;
void Merge(int* A, int p, int q, int r)
{
    int* B=new int[r-p+1];
    int i = p;
    int j = q + 1;
    int k = 0;
    while (i <= q && j <= r) B[k++] = (A[i] <= A[j])?  A[i++] : A[j++];
    while (i <= q) B[k++] = A[i++];
    while (j <= r) B[k++] = A[j++];
    for (i = p; i <= r; i++) A[i] = B[i-p];
    delete B;
}
void MergeSort(int* A, int p, int r)
{
    if (p >= r) return;
    int q = (p + r) / 2;
    MergeSort(A, p, q);
    MergeSort(A, q + 1, r);
    Merge(A, p, q, r); 
}
int main(void)
{
    int A[15]={10,11,12,13,14,0,8,7,6,5,4,3,2,1,9};
    MergeSort(A,0,14);
    for (int i = 0; i<15; i++) cout<<A[i]<<",";
}

//this is another answer:

#include <iostream>
#include <climits>
using namespace std;
static void Merge(int* A, int p, int q, int r)
{
    int n1 = q - p + 1;// A[p..q]
    int n2 = r - q;// A[q+1..r]
    int* L = new int[n1 + 1];
    int* R = new int[n2 + 1];
    int i, j;
    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (i = 0; i < n2; i++)
        R[i] = A[q + i+1];
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = 0;
    j = 0;
    for (int k = p; k <= r; k++)
        A[k] = L[i] <= R[j] ? L[i++] : R[j++];
    delete L;
    delete R;
}
static void Ascending(int* A, int p, int r)
{
    if (p >= r) return;
    int q = (p + r) / 2;
    Ascending(A, p, q);
    Ascending(A, q + 1, r);
    Merge(A, p, q, r);
}
int main()
{
    int A[10]={9,8,7,6,5,4,3,2,1,0};
    Ascending(A,0,9);
    for (int i = 0; i<10; i++)
    {
        cout<<A[i]<<",";
    }
}