Mergesort récursif ne trie que la moitié d'un tableau

Question

J'essaye d'implémenter un algorithme de tri de fusion récursif pour trier un tableau simple d'entiers mais j'obtiens des valeurs étranges pour les index dans la deuxième moitié de mon tableau. La première moitié semble bien trier ce qui est déroutant étant donné que son implémentation récursive. Le tableau des entiers aléatoires est initialisé dans ma méthode principale.

public class MergeSort { 

public static int Rounds = 1; 
public static void MergeSort(Comparable[] ToSort, Comparable[] temp, int first, int last) { 
    if(first < last) { 
     int mid = (first + last)/2; 

     //Test Block 
     System.out.print("For Round " + Rounds + ":\n"); 
     System.out.print("first = " + first + " mid = " + mid + " last = " + last + "\n"); 
     Rounds++; 
     System.out.print("Array in Round " + (Rounds - 1) + " = {"); 
     for(int i = 0; i <= ToSort.length - 1; i++) { 
      System.out.print(ToSort[i]); 
      if(i < ToSort.length - 1) 
       System.out.print(", "); 
      else { 
       System.out.print("}\n\n"); 
      } 
     } 

     MergeSort(ToSort, temp, first, mid); 
     MergeSort(ToSort, temp, mid + 1, last); 
     Merge(ToSort, temp, first, mid + 1, last); 
    } 

} 

public static void Merge(Comparable[] ToSort, Comparable[] temp, int first, int mid, int last) { 
    int beginHalf1 = first; 
    int endHalf1 = mid - 1; 
    int beginHalf2 = mid; 
    int endHalf2 = last; 
    int index = first; 
    int Elements = (last - first) + 1; 

    while(beginHalf1 <= endHalf1 && beginHalf2 <= endHalf2) { 
     if(ToSort[beginHalf1].compareTo(ToSort[beginHalf2]) < 0) temp[index++] = ToSort[beginHalf1++]; 
     else temp[index++] = ToSort[beginHalf2++]; 
    } 

    while(beginHalf1 <= endHalf1) temp[index++] = ToSort[beginHalf1++]; 
    while(beginHalf2 <= endHalf2) temp[index++] = ToSort[beginHalf2++]; 
    for(int i = 0; i < Elements; i++, last--) ToSort[last] = temp[last]; 

} 

}

Ceci produit la sortie suivante:

MATRICE UNSORTED = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87} Pour Round 1 : premier = 0 mi = 4 last = 9 matrice au tour 1 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

Pour la série 2: premier = 0 mid = 2 last = 4 Tableau au Round 2 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

Pour la série 3: premier = 0 mi = 1 last = 2 Array Round 3 = {15, 9, 12, 19 , 49, 43, 57, 70, 78, 87}

Pour la série 4: premier = 0 mi = 0 last = 1 matrice au tour 4 = {15, 9, 12, 19, 49, 43, 57, 70, 78, 87}

Pour la série 5: premier = 3 mi = 3 last = 4 matrice dans la série 5 = {9, 12, 15, 19, 49, 43, 57, 70, 78 , 87}

Pour la série 6: premier = 5 mi = 7 last = 9 matrice dans la série 6 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

Pour la série 7: premier = 5 mi = 6 last = 7 matrice dans la série 7 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

Pour la série 8: premier = 5 mi = 5 last = 6 matrice de la série 8 = {9, 12, 15, 19, 49, 43, 57, 70, 78, 87}

Pour la série 9: première = 8 mi = 8 last = 9 Tableau au tour 9 = {9, 12, 1 5, 19, 49, 43, 57, 70, 78, 87}

Answer 1

Il n'y a pas d'erreur dans votre implémentation. Si vous imprimez votre tableau après application de la méthode MergeSort, il est trié:

Comparable[] a = new Comparable[]{15, 9, 12, 19, 49, 43, 57, 70, 78, 87}; 
Comparable[] b = new Comparable[a.length]; 
MergeSort.MergeSort(a, b, 0, a.length - 1); 

for (int i = 0; i <= a.length - 1; i++) { 
    System.out.print(a[i]); 
    if (i < a.length - 1) 
     System.out.print(", "); 
    else { 
     System.out.print("}\n\n"); 
    } 
} 

imprimera 9, 12, 15, 19, 43, 49, 57, 70, 78, 87}