Javaの再帰Mergesort

Question

私はマージソートのアルゴリズムの質問を練習しています。私は、マージソートのJavaプログラムをビルドします。私は自分のコードに論理的な誤りがあると思います。これは私のコードである

Array length = 6 
    value of q 2 
    value of q 1 
    value of q 0 
9 1073741823 left end -----m(0,0,1) 
6 1073741823 right end -----m(0,0,1) 
remaining element left 
6 9 0 0 0 0 ------------------- 
9 6 1073741823 left end -----m(0,1,2) 
5 1073741823 right end -----m(0,1,2) 
remaining element left 
5 9 6 0 0 0 ------------------- 
value of q 4 
value of q 3 
0 1073741823 left end -----m(3,3,4) 
8 1073741823 right end -----m(3,3,4) 
remaining element right 
5 9 6 0 8 0 ------------------- 
0 8 1073741823 left end -----m(3,4,5) 
2 1073741823 right end -----m(3,4,5) 
remaining element left 
5 9 6 0 2 8 ------------------- 
9 6 5 1073741823 left end -----m(0,2,5) 
0 8 2 1073741823 right end -----m(0,2,5 
remaining element left 
0 8 2 9 6 5 ------------------- 
0 8 2 9 6 5 

：

public class MergeSort{ 
    private int[] digits; 
    private static int[] dummy; 
    private int length; 

    public static void main(String[] args) { 
     int [] digits = {9,6,5,0,8,2}; 
     System.out.println("Array length = "+digits.length); 
     MergeSort ms = new MergeSort(); 
     ms.sort(digits); 


     for(int a :dummy){ 
      System.out.print(a+" "); 
     } 
    } 
    void sort(int [] digits){ 
     this.digits=digits; 
     length=digits.length; 
     dummy= new int[length]; 
     mergesort(0,length-1); 
    } 

    void mergesort(int p,int r){ 
     int q; 
     if(p < r){ 
      q = (p + r)/2; 

      System.out.println("value of q "+q); 
      mergesort(p,q); 
      mergesort(q+1,r); 
      merge(p,q,r); 
      System.out.println("-------------------"); 
     } 
    } 

    void merge(int p,int q,int r){ 
     int i,j,k; 
     int n1=q-p+1; 
     int n2 =r-q; 
     int [] left = new int[n1+1]; 
     int [] right = new int[n2+1]; 
     int [] arr=new int[n1+n2]; 
     for(i = 0; i<n1;i++){ 
      left[i]= digits[p+i]; 
      //System.out.print(left[i]+" "); 
     } 

     for(j = 0; j < n2; j++){ 
      right[j]= digits[q+j+1]; 
      //System.out.print(left[j]+" "); 
     } 
     left[n1] = Integer.MAX_VALUE/2; 
     right[n2] = Integer.MAX_VALUE/2; 

     for(i = 0; i < left.length; i++){ 
      System.out.print(left[i] + " "); 
     } 
     System.out.println("left end -----m("+p+","+q+","+r+")"); 
     for(j = 0; j < right.length; j++){ 
      System.out.print(right[j]+" "); 
     } 
     System.out.println("right end -----m("+p+","+q+","+r+")"); 

     i=0; 
     j=0; 
     for(k = p; k < r; k++){ 
     if(left[i]<right[j]){ 
      dummy[k]=left[i]; 
      i++; 
     } 

     else { 
      dummy[k] = right[j]; 
      j++; 
     } 
    } 

    while(i<n1) 
     dummy[k]=left[i]; 
     i++; 
     k++; 
     System.out.println("remaining element left"); 
    } 

    while(j<n2){ 
     dummy[k]=right[j]; 
     j++; 
     k++; 
     System.out.println("remaining element right"); 
    } 

     for(int a: dummy){ 
      System.out.print(a+" "); 
     } 
    } 
} 

Answer 1

マージソートの場合、それはプレビュー小さい計算結果を取得し、計算の次の段階のためにそれらを使用する必要が動作するように

この

は私の出力でありますあなたの結果はダミーに格納されますが、これはストレージとしてのみ次の計算のソースとして使用されることはありません。私は、マージを行うことがsugestうとマージ機能が値を返すことは、ここでははるかに読みやすく、クリーンである私のバージョンは、（適切なインデント、してください）あなたは

public class MergeSort { 

public static void main(String ...args){ 
    int[]array = {9,6,5,0,8,2}; 
    String sortedResultToPrint = Arrays.toString(sort(array)); 
    System.out.println(sortedResultToPrint); 
} 
public static int[] sort(int[] array) { 
    int[] result = mergSort(array, 0, array.length-1); 
    return result; 
} 

private static int[] mergSort(int[] array, int start, int end) { 
    int[] result = null; 
    if (start < end) { 
     int midle = (start + end)/2; 
     int[] left = mergSort(array, start, midle); 
     int[] right = mergSort(array, midle + 1, end); 
     result = merge(left, right); 
    } else { 
     result = new int[]{array[start]}; 
    } 
    return result; 
} 

private static int[] merge(int[] left, int[] right) { 
    int[] result = new int[left.length + right.length]; 

    int leftPtr = 0; 
    int rightPtr = 0; 
    for (int i = 0; i < result.length; i++) { 
     // Copyed all the left part only right remains 
     if (leftPtr >= left.length) { 
      result[i] = right[rightPtr++]; 
     } 

     // Copyed all the right part only left remains 
     else if (rightPtr >= right.length) { 
      result[i] = left[leftPtr++]; 
     } 

     //Right is smaller than left 
     else if (right[rightPtr] < left[leftPtr]) { 
      result[i] = right[rightPtr++]; 
     } 

     // Left is smaller than right 
     else { 
      result[i] = left[leftPtr++]; 
     } 

    } 
    return result; 
} 

}