Simplest quick sort using one 19-line function This will later be be posted on my website to explain quick sort so I would like how I could improve the readability and simplicity of this demo class. I do not like my use of the stack (meaning this recursion cannot process a list with millions of values).

How could I reduce the stack impact? I think the best way would be not to use as many ArrayList instances. However, I don't know how else because I cannot use lists like int[] list because I do not know their size and surely if I just make it too big the loops will be bigger and take longer.

Here is the class in question:

import java.util.ArrayList;
import java.util.Random;

public class QuickSort {

    static Random r = new Random();

    public static void main(String[] args) {
        int listsize = 100000, range = 100000;
        ArrayList&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();
        for (int i=0; i&lt;listsize; i++)
            list.add(r.nextInt(range));
        sort(list);
        System.out.println(list);
    }

    public static ArrayList&lt;Integer&gt; sort(ArrayList&lt;Integer&gt; list) {
        if (list.size() &lt;= 1) 
            return list;
        int rotationplacement = r.nextInt(list.size());
        int rotation = list.get(rotationplacement);
        list.remove(rotationplacement);
        ArrayList&lt;Integer&gt; lower = new ArrayList&lt;Integer&gt;();
        ArrayList&lt;Integer&gt; higher = new ArrayList&lt;Integer&gt;();
        for (int num : list)
            if (num &lt;= rotation)
                lower.add(num);
            else
                higher.add(num);
        sort(lower);
        sort(higher);

        list.clear();
        list.addAll(lower);
        list.add(rotation);
        list.addAll(higher);
        return list;
    }
}
Rather than creating new Lists, your method could sort the list in place. The method you call recursively could take the list and index values; the methods would look something like this:

/**
 * sorts the {@code list} in place
 */
public static void sort(ArrayList&lt;Integer&gt; list) {
    sort(list, 0, list.size());
}

/**
 * Sorts the {@code list} from {@code fromIndex} to {@code toIndex} - 1.
 */
private static void sort(List&lt;Integer&gt; list, int fromIndex, int toIndex) {

    if (fromIndex == toIndex - 1) {
        return;
    } else {
        // find the pivot, Collections.swap elements, etc...
        // recursively call self.
    }

}


Sorting the list in place reduces the amount of memory on the stack.

Also, to make the code more generic, perhaps you could sort lists of Comparable instead of Integer.