Merge sort fails to sort

I'm hitting a wall with this. I'm trying to implement merge sort to an existing program. (one that utilizes serveral search algorithms) but I'm unable to get the program to sort correctly. The rest of the program works correctly as i've tested with other sort algorithms.


Merge sort code

Code:

---

int mergesort (int a[], int p, int r)
{
        int i;
        int q;
        double x=(p+r)/2;
        if (p<r)
        {
                q= floor (x);
                mergesort (a,p,q);
                mergesort (a,q+1,r);
                merge(a,p,q,r);
              cout << "\n";
        }
        return 0;
}

int merge (int a[], int p, int q, int r)
{
        int k=p;
        int i=0;
        int l=q-1;
        int t[r];
        while ((p<=l)&&(q<=r))
        {
                if (a[p]<=a[q])
                {
                        t[i]=a[p];
                        i++;
                        p++;
                }
                else
                {
                        t[i]=a[q];
                        i++;
                        q++;
                }
        }
        while (p<=l)
        {
                        t[i]=a[p];
                        i++;
                        p++;
        }
        while (q<=r)
        {
                        t[i]=a[q];
                        i++;
                        q++;
        }
        for (i=k; i<=r; i++)
        {
                a[i]=t[i-k];
        }
        return 0;
}

---

Here's my current input/ output arrays

Code:

---

Input
5 8 85 9 78 34 2 6 31 56 7 16 89 476 84 8 22 65 900 76
output
5 8 34 2 6 31 56 7 78 16 84 65 76 85 9 89 476 8 22 900

---

I can see that it's trying to do some sorting, but it's not fully sorting the data.

Any help would be appreciated.

Here's some help.

Name your variables with meaningful names. a and p and q and k and t and l and r don't get it.

Comment your code with what your intentions are.

The ranges that you are merging are not the same as the ranges you have split them into.

When you split, then the first half is p ... q, and second is q + 1 ... r, but when you merge the first half is p ... q - 1 and the second is q ... r.

Incidentally, half-open ranges (where the last index is one beyond the range) seem more intuitive and simpler to use. You can compare against <, and not <=. You won't need to add or subtract one, as the ranges would simply be: [p, q) and [q, r).

Also I don't think you need the double and floor to calculate the middle point, since simple integer division would have the exact same effect.

And lastly, variable sized arrays are non-standard in C++ (GCC's extension).

Code:

---

int t[r]; //this is not allowed in standard C++

---

Quote:

---

Name your variables with meaningful names. a and p and q and k and t and l and r don't get it.

---

Indeed. Picking letters randomly from the alphabet is not a very good naming strategy. Names like first, last and middle would be a great start.

It's working perfectly. Thanks for wading through my code to figure out whats wrong. I'll try to remember to use more usefull variable names from now on.