MergeSort in Java w/ ArrayLists

jumpintofire666

Hey, i can't seem to get my code to sort more than the middle two numbers. ie. INPUT:8,2,6,4 OUTPUT:8,6,4,2
[PHP]import java.util.ArrayList;
public class APMergeSort
{ public static ArrayList<Comparable> mergesort(ArrayList<Comparable> a1)
{ int count = 0;
if (a1.size() == 1 && count == 0)
{ return a1;
}//////////////////////////////////////////fix the a1 = merge(...)
else
{ count += 1;
ArrayList<Comparable> left = new ArrayList<Comparable>();
for(int x = 0; x < a1.size()/2; x++)
{ left.add(a1.get(x));
}System.out.println("left"+left);
ArrayList<Comparable> right = new ArrayList<Comparable>();
for(int x = (a1.size()/2); x <= a1.size()-1; x++)
{ right.add(a1.get(x));
}System.out.println("right"+right);
System.out.println("left:"+left+"||||right"+right);
a1 = merge(a1, left, right);
System.out.println("MERGE"+a1);
return a1;
}
}
public static ArrayList<Comparable> merge(ArrayList<Comparable> a1, ArrayList<Comparable> left, ArrayList<Comparable> right)
{ int lindex = 0;
int rindex = 0;
int index = 0;
a1.clear();
while (lindex < left.size() && rindex < right.size())
{ System.out.println("compare"+(left.get(lindex).compareTo(right.get(rindex))));
if ((left.get(lindex).compareTo(right.get(rindex))) > 0) //x.compareTo(y) < 0
{ System.out.print("fghsdfgd"); //= x>y
a1.add(/*index, */left.get(lindex));
System.out.println("lindex"+lindex);
lindex++;
}
else
{ a1.add(/*index,*/ right.get(rindex));
System.out.println("rindex"+rindex);
rindex++;
}
index++;
System.out.println("a1-firstwhile"+ a1);
}
ArrayList<Comparable> over = new ArrayList<Comparable>();
int oindex;
if (lindex >= left.size())
{ for(int x = 0; x < right.size(); x++)
{ over.add(right.get(x));
System.out.println("zr"+x+" " + over);
}
oindex = rindex;
}
else
{ for(int x = 0; x < left.size(); x++)
{ over.add(left.get(x));
System.out.println("zl"+x+" " + over);
}
oindex = lindex;
}System.out.println("z"+over);
for (int x = oindex; x < over.size(); x++)
{ a1.add(index, over.get(x));
index++;
}
return a1;
}
}
[/PHP]
Can somebody help me figure this out?

jumpintofire666

*note: the oddly placed system.out.println's are a way i was trying to check it.

airbornflght

I'd love to help you but I'm far too tired. Sorry for the useless post.

shwaip

whitespace is your friend.

also, abf, your input is greatly appreciated.

jumpintofire666

Hey, thanx for the input. I've been working and modifying this code. But, ive run into another error. INPUT:9,7,8,6 OUTPUT:9,8,7 Error. The error that im getting is a java.lang.StackOverflowError at java.lang.String.compareTo(Unknown Source). heres the code:
[PHP]import java.util.ArrayList;
public class APMergeSort
{ public static ArrayList<Comparable> mergesort(ArrayList<Comparable> a1)
{ int count = 0;
int lindex = 0;
int rindex = 0;
int index = 0;
if (a1.size() == 1 && count == 0)
{ return a1;
}
else
{ count += 1;
ArrayList<Comparable> left = new ArrayList<Comparable>();
for(int x = 0; x < a1.size()/2; x++)
{ left.add(a1.get(x));
}
ArrayList<Comparable> right = new ArrayList<Comparable>();
for(int x = (a1.size()/2); x <= a1.size()-1; x++)
{ right.add(a1.get(x));
}
a1 = merge(a1, left, right, lindex, rindex, index);
return a1;
}
}
public static ArrayList<Comparable> merge(ArrayList<Comparable> a1, ArrayList<Comparable> left, ArrayList<Comparable> right, int lindex, int rindex, int index)
{ a1.clear();
while (lindex < left.size() && rindex < right.size())
{ if ((left.get(lindex).compareTo(right.get(rindex))) > 0)
{ a1.add(index, left.get(lindex));
lindex++;
}
else
{ a1.add(index, right.get(rindex));
rindex++;
}
index++;
}
if(left.size() != 0 || right.size() != 0)
{ return leftovers(a1, left, right, lindex, rindex, index);
}
else
return a1;
}
public static ArrayList<Comparable> leftovers(ArrayList<Comparable> a1, ArrayList<Comparable> left, ArrayList<Comparable> right, int lindex, int rindex, int index)
{ while(lindex < left.size())
{ int x = 0;
if(a1.get(x).compareTo(left.get(lindex)) < 0)
{ a1.add(x, left.get(lindex));
lindex++;
return leftovers(a1, left, right, lindex, rindex, index);
}
else if(a1.get(x).compareTo(left.get(lindex)) > 0)
{ x++;
return leftovers(a1, left, right, lindex, rindex, index);
}
}
while(rindex < right.size())
{ int x = 0;
if(a1.get(x).compareTo(right.get(rindex)) < 0)
{ a1.add(x, right.get(rindex));
rindex++;
return leftovers(a1, left, right, lindex, rindex, index);
}
else if(a1.get(x).compareTo(right.get(rindex)) > 0)
{ x++;
return leftovers(a1, left, right, lindex, rindex, index);
}
}
return merge(a1, left, right, lindex, rindex, index);
}
}[/PHP]

Through some well placed(not shown here) print statements, i found that the error was being given before the [PHP]a1.add(x, right.get(rindex));[/PHP] in the second while statement of the method leftovers. Can someone help?