Combine sorting gives IndexOutOfBoundsException

Question

The code reads several cases from the file and the size of the arrays, which then arrive, then fills the array and sends it for merge sort.
The problem is that I keep getting index out of bounds and it kills me ...

My debugger just stops working on my eclipse.

 import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class mergesort { public static void mergeSort(int[] array, int first, int last){ int mid; if (first<last){ mid = (last + first)/2; mergeSort(array, first, mid); mergeSort(array, mid+1, last); merge(array, first, last); } } public static void merge(int[] array, int first, int last){ int mid = (last-first)/2; int[] temp = new int[(last-first)]; int a1 = first, a2 = mid + 1, current = 0; while (a1 <=mid && a2<=last){ if (array[a1] <= array[a2]) temp[current++] = array[a1++]; else temp[current++] = array[a2++]; } for (int i = a1; i<=mid; i++) temp[current++] = array[i]; for (int i = a2; i<=last; i++) temp[current++] = array[i]; for (int i =0; i<temp.length; i++) array[first+i] = temp[i]; } public static void main(String[] args) throws FileNotFoundException { File file = new File("sort.in"); Scanner scan = new Scanner(file); int n1 = scan.nextInt(); for (int i = 0; i<n1; i++){ int[] array =new int[scan.nextInt()]; for (int j = 0; j<array.length; j++){ array[j] = scan.nextInt(); } mergeSort(array, 0, (array.length)-1); for (int j = 0; j<array.length; j++){ System.out.println(array[j]); } } } } 

Answer 1

To start, your temp array is too short:

 int[] temp = new int[(last-first)]; 

Since both last and first are inclusive, the above should read:

 int[] temp = new int[last - first + 1]; 

Answer 2

There are several bugs in the merge part of your program (not including the one that NPE showed), first:

 int mid = (last-first)/2; 

it should be:

 int mid = (last+first)/2; 

Secondly, the three for-loop ends at the end work independently - but you should only work on the rest of either a1 / a2.

I implemented it a little differently - perhaps this will help explain the second error:

 public static void mergeSort(int[] arr, int start, int end){ if(start == end) return; // now the recursive calls: // divide the arr: int middle = (end+start)/2; mergeSort(arr, start, middle); mergeSort(arr, middle+1, end); // now merge (conquer) merge(arr, start, end, middle); } private static void merge(int[] arr, int start, int end, int middle) { int[] sorted = new int[end-start+1]; for(int i=start,j=middle+1,index=0; index < sorted.length;){ if(j<=end && arr[i] > arr[j]){ sorted[index] = arr[j]; j++; index++; } else if (i<=middle){ sorted[index] = arr[i]; i++; index++; } else{ sorted[index] = arr[j]; j++; index++; } } // now copy "sorted" to original array for(int i=start,j=0; i<=end; i++,j++){ arr[i] = sorted[j]; } } public static void main(String...args){ int[] arr = {4,2,9,6,2,8,1,9,10,15,12,11}; mergeSort(arr, 0, arr.length - 1); for(int i=0; i<arr.length; i++){ System.out.print(arr[i]+" "); } }