Geek asks and answers

Merge Sort Problem

For my homework in java, I am struggling to write a recursive merge sort class. At the moment, I have 3 driver methods to trigger recursion, a recursive method, mergeSortand a method merge. Depending on which variables are changing, my output is either an array of all zeros, or my original array in the same order. The only thing that the original method mergeSortshould take in one array, and the method mergecan not return anything. Any help with a great rating

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];
        }
    }
}
+5
source share
2 answers

, . , //<= here. mid , a d, 0. == >=, .
. . . O(n^2). , , O(nlog(n)).

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];
    }
}
+1

mergeSort. , :

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

, . ArrayLists :

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);
      }
    }
  }
+3

More articles:


All Articles