javacsvsortingtimsort

Java ArrayList Exception in thread "main" java.lang.NegativeArraySizeException: -28


I have an issue with the sorting algoritm. I use exactly this TimSort for sorting https://www.geeksforgeeks.org/timsort/ (Java). I am reading a CSV file within a loop of first 2500 rows for example.

This is my reading code:

    private void readFile(){
        try{
            int i = 0;
            BufferedReader csvReader = new BufferedReader(new FileReader(this.filename));
            while ((row = csvReader.readLine()) != null){
                String[] entry = row.split(",(?=(?:[^\"]*\"[^\"]*\")*[^\"]*$)", -1);
                if(i > 0 && i <= 2500){
                    int price = Integer.parseInt(entry[5]);
                    entries.add(price);
                }
                i++;
            }
            csvReader.close();

        }catch(Exception e){
            e.printStackTrace();
        }
    }

After that I am converting the string into a int[] Arraylist this way:

public int[] convertArrayList(){
    ArrayList<Integer> arrayList = this.entries;
    int[] converted = new int[arrayList.size()];
    for(int i=1; i < converted.length; i++){
        converted[i] = arrayList.get(i);
    }
    return converted;
}

In my main I have:

    private static synchronized void getPrices(){
        try{
            File dataset = new File("src/CSV/Schools.csv");
            CSVReader reader = new CSVReader(dataset.getCanonicalPath());
            prices = reader.convertArrayList();
        } catch(Exception e){
            e.printStackTrace();
        }
    }

and to run it:

    getPrices();
    int n = prices.length;
    System.out.println(n);

    Instant start = Instant.now();
    System.out.print("Given Array is\n");
    GFG.printArray(prices, n);
    Instant end = Instant.now();

    System.out.println("Time for executing the unsorted array: " + Duration.between(start, end).toNanos());


    GFG.timSort(prices, n);

    Instant start2 = Instant.now();
    System.out.print("\nAfter Sorting Array is\n");
    GFG.printArray(prices, n);
    Instant end2 = Instant.now();

    System.out.println("Time for executing the sorted array: " + Duration.between(start2, end2).toNanos());

Now here is the thing If I run this code with changing the loop to i > 0 && i <= 1000 it's working. But if I take a bigger number like 2500 or 5000 I get the following error:

Exception in thread "main" java.lang.NegativeArraySizeException: -28
at GFG.merge(TimSort.java:32)
at GFG.timSort(TimSort.java:111)
at Main.main(Main.java:27)

It references to the merge method in the TimSort algoritm... I can't fix this any idea's please?


Solution

  • Probably because the TimSort algorithm implementation you linked to is buggy.

    List.sort, Collections.sort, and Arrays.sort(T[]) all already use timsort. There's no need to copy code from random sites to use TimSort. The utility method java.util.Arrays.sort(int[]) uses a dual pivot sort. I would assume that this has better performance characteristics and is therefore used instead of timsort.

    If you're trying to understand the timsort code you linked to, forget all the code you pasted, focus on the timsort impl you linked to, and debug that.