merging two lists

Hi I have really problem with merging two lists in such code like mergesort here is my code and it will throw an exception ,but I do not know why!please help me

private void solve(List<Point> upperHull) {
    list = upperHull;
    number = upperHull.size();
    dcHullForUpperHull(0, number-1 );
}

private void dcHullForUpperHull(int low, int high) {
    /*System.out.println(list);*/
    if (low<high) {
        // Get the index of the Object which is in the middle
        int mid = (low + high) / 2;
        // Sort the left side of the list
        dcHullForUpperHull(low, mid);

        // Sort the Right side of the list
        dcHullForUpperHull(mid +1 , high);

        //combine them both.

        mergeForUpperHull(low, mid, high);
    }
}

private void mergeForUpperHull(int low, int mid, int high) {


    List<Point> auxiliaryList = new ArrayList<Point>();
    List<Point> auxiliaryListTow = new A开发者_JS百科rrayList<Point>();
    for (int i = low; i <= mid; i++) {
    auxiliaryList.add(upperHull.get(i));
    }
    for (int i = mid + 1; i <= high; i++) {
    auxiliaryListTow.add(upperHull.get(i));
    }

    System.out.println(auxiliaryList.get(mid));
    System.out.println(auxiliaryList.get(low));
    }

the below exception is for line : System.out.println(auxiliaryList.get(mid)); exception:

X :166.0  Y: 104.0angle0.0
X :166.0  Y: 104.0angle0.0
Exception in thread "AWT-EventQueue-0" java.lang.IndexOutOfBoundsException: Index: 2, Size: 1
    at java.util.ArrayList.RangeCheck(ArrayList.java:547)
    at java.util.ArrayList.get(ArrayList.java:322)
    at ConvexHull.DCHullVersion.mergeForUpperHull(DCHullVersion.java:142)
    at ConvexHull.DCHullVersion.dcHullForUpperHull(DCHullVersion.java:126)
    at ConvexHull.DCHullVersion.dcHullForUpperHull(DCHullVersion.java:122)

---

for (int i = mid + 1; i <= high; i++) {
    auxiliaryListTow.add(upperHull.get(i));
}

I suppose this is the line causing the exception? Try chaning the i <= high to i < high

It has nothing to do with your function.. the problem is that you'r trying to access an array's field which is not present.

In Java, arrays are starting with a 0 index.

cheers

---

If I am not mistaken, if the list is of size, lets say, 3 or more elements then the

private void mergeForUpperHull(int low, int mid, int high)

method will be called, at some point, with the low and mid parameters both having the same value, higher than 0. This will definitely cause the exception you encounter when you try to do this System.out.println(auxiliaryList.get(mid));
Try debugging your code, line by line, it might help you.
I'm just curios though, why are you doing this? Your code excerpt leaves a lot to be guessed and to be honest, it doesn't make much sense(at least not to me).

---

The reason that you are getting an IndexOutOfBoundsException is because you are creating a brand new List<Point> auxiliaryList every time mergeForUpperHull is called. So, in the scenario where, low = mid = 2, you will have inserted (added) only one element in the new auxiliaryList, which will not correspond to the mid index that you are trying to get from the auxiliaryList in the system out.

There are other issues with the code, but I will assume that you are simply in scratch pad mode. But to give you some valid direction, I would not use two auxiliary lists in a merge method, instead I will use the master list to perform compare and swap operations. Remember, that if you simply add to an auxiliary list for every merge operation, you will have more data in the final list as a result of bubbling up from the recursive dcHullForUpperHull calls.

To be more precise, you will end up having (Log2(size of list)+1)*(size of list) elements from the merge you are performing (assuming that you don't create a brand new list each time)

Divide and conquer algorithms are great learning exercises, so I will not spit out the complete code here, but the above should be decent direction for you to complete the aforementioned merge sort