Trouble with Merge Sort

Question

For my java homework I am struggling to write a recursive merge sort class. As of right now I have 3 method a "driver" method to start the recursion, the recursive mergeSort method and a merge method. Depending on what variables I change my output is either an array of all zeros or my original array in the same order. The only thing is the original mergeSort method must take in one array and the merge method cannot return anything. Any help with be much appreciated

import java.util.Arrays;
public class merge2 {
    public static void main(String[] args){
        int []a={22,45,1,4,89,7,0};
        mergeSort(a);
        System.out.println(Arrays.toString(a));                 
    }

    public static void mergeSort(int [] a){
        mergeSort(a,0,a.length-1);
    }

    public static void mergeSort(int []a, int beg,int end){
        if(beg<end){
            int mid=(beg+end)/2;
            mergeSort(a,beg,mid);
            mergeSort(a,mid+1,end);
            merge(a,beg,mid,end);
        }
    }

    private static void merge(int []a, int beg, int middle, int end){
        int [] d=new int[a.length];
        int mid=middle+1; //start of second half of array
        for(int i=0;i<d.length;i++){
            if(beg<=middle && mid<=end){  
                if(a[beg]<=a[mid]) {
                d[i]=a[beg];
                beg++;
                } else if(a[mid]<=a[beg]){
                        d[i]=a[mid];
                        mid++;
                }
            }else if(beg>middle){ 
                d[i]=a[mid];
                mid++;
            }else if(mid==a.length){
                d[i]=a[beg];
                beg++;
            }
        }
        for(int w=0;w<d.length;w++){
            a[w]=d[w];
        }
    }
}

Answer 1

Here is pseudocode for the mergeSort method. I see that you have disregarded the base cases for one or two elements:

if (sublist has only one value)
   do nothing
else if (sublist has two values)
   switch if necessary
else    // recursion, divide list into two halves
   Find midpoint of current sublist
   Call mergeSort and process left sublist
   Call mergeSort and process right sublist
   merge left and right sublists

As for your merge method, it is creating a new array instead of modifying the existing array. I suggest using ArrayLists to implement it:

private void merge(int[] a, int first, int mid, int last)
  {
    ArrayList<Integer> left = new ArrayList<Integer>(mid - first + 1), right = new ArrayList<Integer>(last - mid);
    for(int m = first; m <= mid; ++m)   //initialize left sublist
    {
      left.add(a[m]);
    }
    for(int m = mid + 1; m <= last; ++m)    //initialize right sublist
    {
      right.add(a[m]);
    }
    int i = first;
    while(!left.isEmpty() || !right.isEmpty())  //while either list has an element
    {
      if(left.isEmpty())
      {
        a[i++] = right.remove(0);
      }
      else if(right.isEmpty())
      {
        a[i++] = left.remove(0);
      }
      else if (left.get(0) < right.get(0))
      {
        a[i++] = left.remove(0);
      }
      else
      {
        a[i++] = right.remove(0);
      }
    }
  }

Answer 2

Ok I fixed your solution. Your main problem was on line marked with //<= here. When mid run over end index you were not assigning values from a to d so it was left filled with 0. You had to replace == with >= to overcome this issue.
I also fixed your work with indexes. You don't have to run over whole array on each level. Also your complexity suffers this way. I think its about O(n^2). It's enough to run only over part of array which is processed on this recursion level to keep with O(nlog(n)) complexity.

Fixed algorithm follows

public static void main(String[] args){
    int []a={22,45,1,4,89,7,0};
    mergeSort(a);
    System.out.println(Arrays.toString(a));

}

public static void mergeSort(int [] a){
    mergeSort(a,0,a.length-1);
}

public static void mergeSort(int []a, int beg,int end){
    if(beg<end){
        int mid=(beg+end)/2;
        mergeSort(a,beg,mid);
        mergeSort(a,mid+1,end);
        merge(a,beg,mid,end);
    }
}

private static void merge(int []a, int beg, int middle, int end){
    int [] d=new int[a.length];
    int mid=middle+1; //start of second half of array
    int beg1=beg;
    for(int i=beg1;i<=end;i++){
        if(beg<=middle && mid<=end){  
            if(a[beg]<=a[mid]) {
            d[i]=a[beg];
            beg++;
            } else if(a[mid]<=a[beg]){
                    d[i]=a[mid];
                    mid++;
            }
        }else if(beg>middle){         
            d[i]=a[mid];
            mid++;
        }else if(mid>=end){ //<= here
            d[i]=a[beg];
            beg++;
        }
    }
    for(int w=beg1;w<=end;w++){
        a[w]=d[w];
    }
}