StackOverFlowError for quicksort Java

Question

I am testing a quicksort code I wrote but I'm not sure why I am getting

error:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList$Itr.<init>(ArrayList.java:820)
    at java.util.ArrayList.iterator(ArrayList.java:814)
    at practice.Quicksort.quicksort(Quicksort.java:15)
    at practice.Quicksort.quicksort(Quicksort.java:25)
    at practice.Quicksort.quicksort(Quicksort.java:25)
    at practice.Quicksort.quicksort(Quicksort.java:25)

where line 15 is:

for (int n : arr) {

and line 25 is:

more = quicksort(more);

code:

public class Quicksort {
    public static List<Integer> quicksort(List<Integer> arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        List<Integer> less = new ArrayList<Integer>();
        List<Integer> more = new ArrayList<Integer>();
        int pivotIndex = arr.size() / 2;
        int pivot = arr.get(pivotIndex);
        for (int n : arr) {
            if (n < pivot) {
                less.add(n);
            }
            else {
                more.add(n);
            }
        }
        // recursively sort
        less = quicksort(less);
        more = quicksort(more);

        // concatenate all
        less.add(pivot);
        less.addAll(more);
        return less;
    }

    public static void main(String[] args) {
        List<Integer> test = new ArrayList<Integer>();
        int[] arr = {2,4,1,4,5,2,-10,3,0,33,23};
        for (int c : arr) {
            test.add(c);
        }
        System.out.println(quicksort(test));
    }
}

Answer 1

Your code has a fundamental flaw, which increases the possibility of the list named more being same in two subsequent iterations. Possible issues lie in the below section of the code:

 int pivotIndex = arr.size() / 2;
    int pivot = arr.get(pivotIndex);
    for (int n : arr) {
        if (n < pivot) {
            less.add(n);
        }
        else {
            more.add(n);
        }
    }

Do not add the pivot in the more or less list. Moreover, you can understand how to choose the variant here on the blog

Answer 2

The list more should not include the pivot. If it does your run the risk of more being exactly the same list that was passed in, and you get an infinite recursive loop until the program runs out of stack space.

A common technique is swapping the pivot with the first item in the list, and then create the lists of less and more starting from the second item.