I am working on a merge sorting algorithm and cannot find my error. The output is mostly sorted until the end where it lists several of the ints randomly:

1 2 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91 92 93 95 96 97 98 99 100 30 13 14 83 94

    

    public static void main(String args[]) throws IOException {



        Scanner scan = new Scanner(System.in);
        System.out.println("Enter dataset size: ");
        int size = scan.nextInt();
        String file = ""   size   ".txt";
        
        scan.close();
        Scanner scanner = new Scanner(new File(file));
        
        
        

        // read numbers from text file into the array
        // set array size to the user input size
        // while loop reads text file until each int is read
        int array[] = new int[size];
        int i = 0;
        while(scanner.hasNext()) {
            array[i  ] = scanner.nextInt();
        }
        scanner.close();
        
        
        
        
        // create 4 copies of the array to test each in a separate algorithm
        int array1[] = new int[size];
        int array2[] = new int[size];
        int array3[] = new int[size];
        int array4[] = new int[size];
        for (int j = 0; j < array.length; j  ) {
            array1[j] = array[j];
            array2[j] = array[j];
            array3[j] = array[j];
            array4[j] = array[j];
        }
        
        

        
        // test bubble sort
        // this inputs the array and outputs time taken to compute
        bubbleSort(array1);
        

        // test selection sort
        // this inputs the array and outputs time taken to compute
        selectionSort(array2);


        
        
        //quickSort(array3, 0, array3[array3.length-1]);
        
        // test merge sorting algorithm

        mergeSort(array4, 0, array4[array4.length-1]);

        

        System.out.println();
        for (int k = 0; k<array4.length; k  ) {
            System.out.print(array4[k]   " ");
        }

        
        

    }

public static void mergeSort(int arr[], int start, int end) {
        if (start < end) {
            int mid = (start   end)/2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid 1, end);
            merge(arr, start, mid, end);
        }

    }
    
    
    private static void merge(int arr[], int start, int mid, int end) {
        int n1 = mid - start   1;
        int n2 = end - mid;
        int left[] = new int[n1];
        int right[] = new int[n2];
        for (int i = 0; i <n1; i  ) {
            left[i] = arr[start i];
        }
        for (int j = 0; j < n2; j  ) {
            right[j] = arr[mid   1   j];
        }
        
        int i = 0; 
        int j = 0; 
        int k = start;
        
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i  ;
            } else {
                arr[k] = right[j];
                j  ;
            }
            k  ;
        }
        
        while (i < n1) {
            arr[k] = left[i];
            i  ;
            k  ;
        }
        
        while (j < n2) {
            arr[k] = right[j];
            j  ;
            k  ;
        }

    }

CodePudding user response：

The problem is in how you call your mergeSort:

// test merge sorting algorithm
mergeSort(array4, 0, array4[array4.length-1]);

Try replacing array4[array4.length-1] with just array4.length-1.