Infinite loop/recursion when implement quicksort in java

I'm attempting to implement quicksort in java in order to count the number of comparisons made, but I'm running into an infinite loop/recursive call situation, and I can't quite figure out where it's coming from.

Through debugging I've determined that the inner for loop runs however many times, and everything is only entered into "less" sublist, and then a recursive call is made to quicksort(less)

    private ArrayList<Comparable> quickSort(ArrayList<Comparable> qList) {开发者_如何学Go
            ArrayList<Comparable> less = new ArrayList<Comparable>();
            ArrayList<Comparable> greater = new ArrayList<Comparable>();
            if (qList.size() <= 1)
                return qList;
            Comparable pivot = qList.get(qList.size() / 2);
            for (int i = 0; i < qList.size(); i++) {
                if ((qList.get(i).compareTo(pivot)) <= 0) {
                    comps++;
                    less.add(qList.get(i));
                } else {
                    comps++;
                    greater.add(qList.get(i));
                }
            }

            ArrayList<Comparable> toReturn = new ArrayList<Comparable>(
                    quickSort(less));
            toReturn.add(pivot);
            toReturn.addAll(quickSort(greater));
            return toReturn;

        }

If I just run the code with a list of size 20, I get this error

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Arrays.copyOf(Unknown Source)
    at java.util.ArrayList.ensureCapacity(Unknown Source)
    at java.util.ArrayList.add(Unknown Source)
    at file.quickSort(CMSC351P1.thisClass:40)
    at file.quickSort(CMSC351P1.thisClass:48)

The problem is that you add the pivot element itself to the 'less' list so the base case never terminates.

Example: You sort the list [0, 0] with your algorithm. The pivot element is ... 0. The 'less' list that your algorithm produces is again [0, 0], and you enter in infinite loop.

You don't exclude the pivot from the less/greater sublists -- in fact, you explicitly include it in the sublist set. I suspect this means you'll get stuck with lists of two being infinitely sorted in many cases. You'll need to exclude the pivot from the less sublist.

You don't ensure that you partition the list so that the greater list is decreased in size by 1 or more or the less list is decreased in size by 1 or more.

At some point, if the pivot is the largest element in the list, then everything will go to the "less" list.

When you call it, the same thing will happen again.