Merge Sort with reading data from file

Question

What is wrong with my code? I am reading data from a file which consists of 1 number per line and using merge sort to sort it. I am getting following error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
       at MergeSort.merge(MergeSort.java:67)
       at MergeSort.sort(MergeSort.java:30)
       at MergeSort.main(MergeSort.java:86)

TextFile:

300
40
512
234
100

Is there anything wrong in my mergeSort implementation?

Here is my code:

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class MergeSort
{
    void sort(int[] arr, int low, int high)
    {
        if(high > low)
        {   

        int mid = (low + high)/2;
        sort(arr,low,mid);

        sort(arr,mid+1,high);

        merge(arr, low, mid+1, high);
        }
    }
    void merge(int arr[], int low,int mid, int high)
    {
        int helper[] = new int[arr.length];

        //copy both halves into helper
        for(int i=0;i< arr.length;i++)
        {
            helper[i] = arr[i];
        }

        //compare elements from left & right, initialize variables
        int helperLeft = low;
        int helperRight = high;
        int curr = mid+1;

        //while if left<=mid && mid+1 <=right && if left < right assign lowest elem to original array
        while(helperLeft <= curr && curr <=helperRight)
        {
            if(helperLeft <= curr)
            {
                arr[helperLeft] = helperLeft;
                helperLeft++;
            }
            else
            {
                arr[curr] = curr;
                curr++;
            }
            helperRight++;
        }
        //copy all elements to arr
        int rem = mid-helperLeft;
        for(int i=0;i<rem;i++)
        {
            arr[helperRight+i] = helper[helperLeft+i];
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub

        MergeSort pb = new MergeSort();

        InputStream inputStream = new FileInputStream("task.txt");
        @SuppressWarnings("resource")
        BufferedReader R = new BufferedReader(new InputStreamReader(inputStream));
        int arraySize = Integer.parseInt(R.readLine());
        int[] inputArray = new int[arraySize];
        for (int i = 0; i < arraySize; i++) {
            inputArray[i] = Integer.parseInt(R.readLine());
        }

        pb.sort(inputArray, 0, inputArray.length-1);

        for (int j = 0; j < inputArray.length; j++) {
            System.out.println(inputArray[j]);
        }
    }
}

New Exception:

Exception in thread "main" java.lang.NumberFormatException: null
    at java.lang.Integer.parseInt(Unknown Source)
    at java.lang.Integer.parseInt(Unknown Source)
    at coursera.MergeSort.main(MergeSort.java:74)

Answer 1

Try this:

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class MergeSort {    
    public void mergeSort(Integer[] array, int lo, int n) {
        int low = lo;
        int high = n;
        if (low >= high) {
            return;
        }

        int middle = (low + high) / 2;
        mergeSort(array, low, middle);
        mergeSort(array, middle + 1, high);
        int end_low = middle;
        int start_high = middle + 1;
        while ((lo <= end_low) && (start_high <= high)) {
            if (array[low] < array[start_high]) {
                low++;
            } else {
                int Temp = array[start_high];
                for (int k = start_high - 1; k >= low; k--) {
                    array[k + 1] = array[k];
                }
                array[low] = Temp;
                low++;
                end_low++;
                start_high++;
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        MergeSort pb = new MergeSort();
        try {
            BufferedReader br = new BufferedReader(new FileReader("E:\\task.txt"));
            List<Integer> lines = new ArrayList<Integer>();
            String line;
            while ((line = br.readLine()) != null) {
                lines.add(Integer.parseInt(line));
            }
            br.close();
            Integer[] inputArray = lines.toArray(new Integer[lines.size()]);
            pb.mergeSort(inputArray, 0, inputArray.length - 1);
            for (Integer i : inputArray) {
                System.out.println(i);
            }
        } catch (IOException ie) {
            System.out.print(ie.getMessage());
        }

    }
}

Answer 2

Apart from the exception, I don't think your merge logic is correct. Look at your codes:

 while(helperLeft <= curr && curr <=helperRight)
        {
            if(helperLeft <= curr)
            {
                arr[helperLeft] = helperLeft;
                helperLeft++;
            }
            else
            {
                arr[curr] = curr;
                curr++;
            }
            helperRight++;
        }

here, helperLeft, helperRight and curr are all array indexes. You are setting the array element with indexes, like a[23]=23. it is not correct. In MergeSort's merge, we should compare elements from left and right and do merge, not indexes.

I suggest that write a unittest for your mergesort, to make sure it works for all cases (including corner cases) then invoke your method in your real codes.

Also would it be fine if your MergeSort.sort() is a static?

I implemented a merge() too, you can check here : https://github.com/sk1418/jalgorithm/blob/master/src/main/java/com/kent/algorithm/sorting/MergeSort.java#L130

hope it helps.

Answer 3

I think the problem is in the while condition

while(helperLeft <= curr && curr <=helperRight)

In this you never check if helperLeft or helperRight exceed the Array index. Modify it as folows :

while(helperLeft < arr.length
     && helperRight< arr.length
     &&  helperLeft <= curr 
     && curr <=helperRight)
{
  // do something
}