Merge Sort > Arrays.copyOfRange

[Zren]

What seems to be wrong here. I'm getting an error for:
left = MergeSort( Arrays.copyOfRange( a, 0, middle-1 ) );

java.lang.IllegalArgumentException: 0 > -1
at java.util.Arrays.copyOfRange(Arrays.java:3136)

Is it my logic or is it just me using the method improperly. I think it's my logic but I'm not entirely sure.

Java:

public static int[] copyOfRange(int[] original, int from, int to) {         int newLength = to - from;         if (newLength < 0)             throw new IllegalArgumentException(from + " > " + to);         int[] copy = new int[newLength];         System.arraycopy(original, from, copy, 0,                          Math.min(original.length - from, newLength));         return copy;     }         public static int[] MergeSort(int[] a) {                 if ( a.length <= 1) {                         return a;                 }                                 int[] left, right;                                 int middle = (a.length / 2) - 1;                 left = MergeSort( Arrays.copyOfRange( a, 0, middle-1 ) );                 right = MergeSort( Arrays.copyOfRange( a, middle, a.length ) );                                 if ( left[left.length-1] > right[right.length-1] ) {                         return merge( left, right );                 } else {                         return append( left, right );                 }         }

[Vermette]

Trace your code with an array of length 2.

edit: Also, line 3136?!?? Are you trying to build a God Object?

[Zren]

It's line 3163 in the java.util.Arrays class dude. Tell the people who design the Java API that.

[DemonWasp]

Remember that array.length > index of last element in the array for arrays indexed from 0 (like Java). Your second copyOfRange is the one that's causing the issue, I think.

[Vermette]

DemonWasp @ May 9th 2009, 16:39 wrote:

Remember that array.length > index of last element in the array for arrays indexed from 0 (like Java). Your second copyOfRange is the one that's causing the issue, I think.

Nah it's definitely the first use. Like I said, try an array of length 2.

edit: Zren, apologies; I read fast and assumed the line number was from your own code.

[riveryu]

I think the problem may lie with your interpretation of merge sort.

- When you used "Arrays.copyOfRange" and passing it recursively, it simply creates an entirely new array and does not relate back the original array to be sorted. It was a good try at simplifying your code but you cannot do that...

- Merge sort assumes 2 sublists are sorted, but they are not sorted all together even if the last elements follow each other.
Thats why you have merge method to put them together and keep them sorted.

Consider:
left 1 2 3 4
right 1 2 3 5
According to your code, it will append right to left yielding 1 2 3 4 1 2 3 5, which is not what you want....

You should look at more stuff on the logic and idea behind merge sort and recursion.
Hope this helps.

[Vermette]

Ok I guess it has been long enough. Here is what I am referring to:

Java:

if ( a.length <= 1) {     return a; } int middle = (a.length / 2) - 1;

When a.length == 2, the if statement is passed over. middle becomes 0.

Java:

left = MergeSort( Arrays.copyOfRange( a, 0, middle-1 ) );

So the exception is being thrown for the above, as you copy from a range of 0 to -1. There's more work yet to fix this code, but this is the cause of the above exception.

[Zren]

This is actually an intepretation of someone else's code after I googled 'java merge sort'. I was trying to find out how to code this algorithm with a working example, but everything I found was either too complex or didn't work when I re-typed it. Thank you for pointing out the problem though. I understand the algorithm itself, it's just I needed an example to push me through. (Like Fibinacci helps with basic Recursion.)

I found another one that works and is much simple to understand. It follows more or less the example on this site except for the where it actually does the sorting and all java-ified.

Sorry for not posting, I got busy search for other sorts and managed to get them working.