MergeSort

[TemetNosce]

I need to derive a MergeSort program from some given Pseudocode and implement it into a given program code. Now, I tried my best, but it's not doing, what it's supposed to.
If someone could find my mistake and help me out, I'd be thrilled ^^

first pseudocode:

MERGE-SORT(A, p, r)
1 if p<r then //check for recursion
2 q <- (p+r)/2 //q rounded down, separate
3 MERGE-SORT(A,p,q) //sort left field
4 MERGE-SORT(A,q+1,r) //sort right field
5 MERGE(A,p,q,r) //merge fields

first call: MERGE-SORT(A,1,n)

second pseudocode (for MERGE):

MERGE(A,p,q,r){
n1 <- q-p+1
n2 <- r-q
//create holders L[1...n1+1] and R[1...n2+1]
FOR i <- 1 TO n1 DO
L[i] <- A[p+i-1]
FOR j <- 1 TO n2 DO
R[j] <- A[q+j]
L[n1+1] <- +inf ; R[n2+1] <- +inf;
i <- 1; j <- 1;
FOR k <- p TO r DO
IF L[i]<=R[j]
THEN A[k] <- L[i]; i <- i+1
ELSE A[k] <- R[j]; j <- j+1
}





and here's the code i need to implement it in:

1 template <c l a s s T>
2 c l a s s S o r t in g Alg o r it h m
3 {
4 public :
5 vi rtual void s o r t (T∗ , unsigned i nt ) = 0 ;
6 } ;
7
8 template <c l a s s T>
9 c l a s s MergeSort : public So r t ing Alg o r it hm<T>
10 {
11 public :
12 void s o r t (T∗ , unsigned i nt s i z e ) ;
13 } ;
14
15 template <c l a s s T>
16 void MergeSort<T>:: s o r t (T∗ a , unsigned i nt s i z e )
17 {
18 // your implementation here
19 }
20
21 typedef MergeSort<i nt> I nt Mer g eSo r t ;

[TemetNosce]

this is my program (i went ahead and changed it into int, hoping to make less mistakes. i dont receive any errors, but the field does not get sorted. numbers from the field just disappear and get replaced by other random ones)


#include <iostream>
#include <math.h>

using namespace std;

int sort(int* a,unsigned int size)
{
int p=1;
int r=size;
if(p<r)
{
int q=(p+r)/2;

//sort left side
if(p<q)
sort(a,q);

//sort right side
if(q+1<r)
{
int bla=r-q-1;
sort(a,bla);
}



//merge
int n1=q-p+1;
int n2=r-q;

//create L and R holder thingies
int L[n1+1];
int R[n2+1];
for(int i=1;i<n1;i++)
L[i]=a[p+i-1];
for(int j=1;j<n2;j++)
R[j]=a[q+1];
L[n1]=INFINITY;
R[n2]=INFINITY;
int i=1;
int j=1;
for(int k=p;k<=r;k++)
{
if (L[i]<R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
}
}
}
}

//this is just my main, to check if it s working

int main()
{

int x[5]={87,13,0,4,5};
sort(x,5);

for(int i=0;i<5;i++)
cout << x[i]<< " " << endl;

return 0;
}

[ne555]

[code] "Please use code tags" [/code]

The divide par

//sort left side
if(p<q)
sort(a,q);

//sort right side
if(q+1<r)
{
int bla=r-q-1;
sort(a,bla); //where does the right part start? 

//merge
int n1=q-p+1;
int n2=r-q;

//create L and R holder thingies
int L[n1+1]; //variable length array is forbidden by the standard
int R[n2+1];

for(int i=1;i<n1;i++) //why i starts at 1?
  L[i]=a[p+i-1]; // p=1 so a[1] to a[n1]. You want a[0] to a[n1-1]
for(int j=1;j<n2;j++) //same here
  R[j]=a[q+1];  //miss something. 'a' doesn't change its index. R[j] = a[42]

int i=1; //why starts at 1? why is declared outside?
int j=1;
for(int k=p;k<=r;k++) //a[1] to a[size] (out of bounds) 
{
  if (L[i]<R[j])
  {
    a[k]=L[i];
    i++;
  }
  else
  {
    a[k]=R[j];
    j++;
  }
}