Merge sort Java Algorithm

Question

Эй, у меня были проблемы с моей сортировкой слияний, я знаю, что в Интернете много информации, и это появилось несколько раз, но я не знаю, что происходит, независимо от того, что я делаю, это не будет работать, какая-то помощь была бы оценена Спасибо

Мой главный метод выглядит следующим образом:

for (int i = 0; i < trials; i++) { 
     data = generateRandomArray(arraySize); 

     // You can use following line to print out data for debugging 
     System.out.println("The array is: " + getString(data)); 

     // ADD YOUR CODE HERE TO SORT DATA AND CALCULATE EXECUTION TIME 

     // System.out.println("first index:" + data[0]); 
     // System.out.println("first index:" + data[arraySize-1]); 

     //System.out.println("hello " + SortArray.basicPartition(data,0,data.length-1)); 
     SortArray.mergeSort(data, 0, data.length-1); 

     if (isSorted(data)) 
      System.out.println(" passes - array is sorted"); 
     else 
      System.out.println(" failed - array is not sorted"); 

---

public static <T extends Comparable<? super T>> 
void mergeSort(T[] a, T[] tempArray, int first, int last){ 
    if(first < last)  // We have some work to do 
    { 
     int mid = first+(last-first)/2; 
     mergeSort(a, tempArray, first, mid); 
     mergeSort(a, tempArray, mid+1, last); 
     merge(a, tempArray, first, mid, last); 
    } 
} // end mergeSort 

/** Merge the entries in two contiguous sorted sublists 
* @param a An array of Comparable objects. 
* @param tempArray A temporary array used in the merge. 
* @param first An integer >= 0 and < mid. 
* @param mid An integer <= last. 
* @param last An integer < a.length. 
*/ 
public static <T extends Comparable<? super T>> 
void merge(T[] a, T[] tempArray, int first, int mid, int last){ 

    int firstIndex = first; 
    int FirstHalfEnd = mid -1; 


    while ((first <= FirstHalfEnd) && (mid <= last)) { 

     if (a[first].compareTo(a[mid]) <= 0) { 

      tempArray[firstIndex] = a[first]; // last to first 
      firstIndex++; 
      first++; 
     } 
     else { 
      tempArray[firstIndex] = a[mid]; 
      FirstHalfEnd++; 
      mid++; 
      //System.out.println("out of bounds"); 
     } 
    } 

    while (first <= FirstHalfEnd) { 
     tempArray[firstIndex] = a[first]; 
     firstIndex++; 
     first++; 

    } 
    while(mid <= last){ 
     tempArray[firstIndex] = a[mid]; 
     firstIndex++; 
     mid++; 
    } 
    for(int i=0;i<(last-first+1);i++){ 
     a[last] = tempArray[last]; 
     last--; 
     //System.out.println(a[i]); 
    } 

} // end merge 

---

OUTPU T

The array is: [ 1 5 3 5 1 6 9 7 1 4 ] 
    failed - array is not sorted 
The array is: [ 1 8 3 4 3 1 6 8 0 9 ] 
    failed - array is not sorted 
The array is: [ 0 1 5 5 5 0 0 3 0 4 ] 
    failed - array is not sorted 
The array is: [ 0 0 6 2 7 4 6 2 2 2 ] 
    failed - array is not sorted 
The array is: [ 4 9 2 3 3 4 4 0 3 5 ] 
    failed - array is not sorted 

Answer 1

Я не запускать свой код - есть недостающие части -, но я заметил 2 проблемы в первом while цикла в функции merge() - см добавлены комментарии:

while ((first <= FirstHalfEnd) && (mid <= last)) { 

    // compareTo return a negative value if (a[first] < a[mid]) 
    // Then I think your comment is wrong: the values are put in the 
    // temporary array in increasing order. It means you have to review 
    // the for loop that copies the values 
    // at the end. 
    if (a[first].compareTo(a[mid]) <= 0) { 

     tempArray[firstIndex] = a[first]; // last to first (No!) 
     firstIndex++; 
     first++; 
    } 
    else { 
     tempArray[firstIndex] = a[mid]; 
     FirstHalfEnd++; // <= this a bug, should be firstIndex++ 
     mid++; 
     //System.out.println("out of bounds"); 
    } 
} 

EDIT
Поскольку значения в порядке возрастания в tempArray, цикл копирования for должно быть что-то вместе:

for(int i = first; i <= last; ++){ 
    a[i] = tempArray[i]; 
} 

Что может быть упрощена (?) Или оптимизируется

System.arraycopy(tempArray, first, a, first, (last-first+1)); 

Answer 2

Вот альтернативная реализация. Он сортирует в порядке убывания:

public class MergeSort { 
public static void merge(int[]a,int[] aux, int f, int m, int l) { 

    for (int k = f; k <= l; k++) { 
     aux[k] = a[k]; 
    } 

    int i = f, j = m+1; 
    for (int k = f; k <= l; k++) { 
     if(i>m) a[k]=aux[j++]; 
     else if (j>l) a[k]=aux[i++]; 
     else if(aux[j] > aux[i]) a[k]=aux[j++]; 
     else a[k]=aux[i++]; 
    }  
} 
public static void sort(int[]a,int[] aux, int f, int l) { 
    if (l<=f) return; 
    int m = f + (l-f)/2; 
    sort(a, aux, f, m); 
    sort(a, aux, m+1, l); 
    merge(a, aux, f, m, l); 
} 
public static int[] sort(int[]a) { 
    int[] aux = new int[a.length]; 
    sort(a, aux, 0, a.length-1); 
    return a; 
} 

}