Probleme mit Rekursion bei der Verwendung von Merge Sort zum Zählen der Inversion in Java

Question

Dieser Code ist für Problem, wo es eine Datei mit 100000 Ganzzahlen gibt, jeder in einer Zeile, die 100000 geordnete ganze Zahlen in einem Array sein soll. Ziel ist es, die Anzahl der Inversionen zu zählen (wenn eine Zahl rechts im Array größer ist als eine Zahl links). Die Implementierung soll Mischsort verwenden. Wenn beim Zusammenführen von linkem und rechtem Unterfeld noch Werte im linken Unterfeld verbleiben, wenn ein Wert vom rechten Unterfeld für das Zusammenführen verwendet wird, wird die Anzahl der im linken Unterfeld verbliebenen Werte auf die gesamte Inversionszählung erhöht.

Mein Code nicht die richtige Anzahl von Umkehrungen für einfache Fälle zurückkehren, so denke ich, das Problem in meinem Code in der Rekursion ist, oder die drei Linien

mergeSort(left); 
mergeSort(right); 
merge(ii, left, right); 

Ich kann den Grund herauszufinden, ich bin nicht die richtige Anzahl von Inversionen erhalten. Am wahrscheinlichsten ist es, weil ich Inversionen mehr inkrementieren sollte, wenn ich die linken und rechten Subarrays zusammenfasse, aber ich habe den Fehler noch nicht herausgefunden.

import java.io.*; 
import java.util.*; 

public class Inversion { 

    public static int inversions = 0; 
    public static void main(String[] args) throws FileNotFoundException{ 
     // TODO Auto-generated method stub 

     int[] list = new int[100000]; 
     Scanner sc = new Scanner(new File("src/inversion.txt")); 
     for(int i = 0; i < 100000; i++) 
     { 
      list[i]=sc.nextInt(); 
     } 

     System.out.println(inversions); 

     sc.close(); 
    } 
    public static void mergeSort(int[] ii) 
    { 
     if (ii.length > 1) 
     { 
     int[]left = Arrays.copyOfRange(ii, 0, ii.length/2); 
     int[]right = Arrays.copyOfRange(ii, ii.length/2, ii.length); 

     mergeSort(left); 
     mergeSort(right); 
     merge(ii, left, right); 
     } 

    } 
    public static void merge(int[]result, int[]left, int[]right) 
    { 
     int ileft=0; 
     int iright=0; 
     for (int i = 0; i < result.length; i++) 
     { 
      if (iright>=right.length || (ileft < left.length && left[ileft] <= right[iright])) 
      { 
       result[i]=left[ileft++]; 
      } 
      else 
      { 
       result[i]=right[iright++]; 
       inversions += left.length-ileft; 
      } 
     } 
    } 
} 

Answer 1

In Ihrem public static void mergeSort(int[] ii) Methode in if (ii.length > 1) sollten Sie, wenn ii.length >= 2 werden überprüft, da der Merge-Sort-Algorithmus das Array in zwei Hälften teilt, die, warum Sie durch 2 in Arrays.copyOfRange teilen ist. 1 kann nicht in eine ganze Zahl geteilt werden, wenn sie in zwei Hälften geteilt wird.

In merge versuchen left[ileft] < right[iright] statt left[ileft] <= right[iright]