Implementation of http://en.wikipedia.org/wiki/Quicksort#Simple_version

NotSoQuickSort.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * Implementation of http://en.wikipedia.org/wiki/Quicksort#Simple_version.
 */
public class NotSoQuickSort {

    private static final Random random = new Random();

    public static void main(String[] args) {


        final int[] arr = new int[15];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }

        System.out.println("initial array: " + Arrays.toString(arr));

        int[] sorted = sort(arr);

        System.out.println("sorted array: " + Arrays.toString(sorted));
    }

    // Can't believe there's not a better way to do this...
    // See http://stackoverflow.com/q/718554/7507
    private static int[] sort(List<Integer> listOfInts){

        final int[] tmp = new int[listOfInts.size()];

        for(Integer val : listOfInts) {
            if(val != null) {
                tmp[i] = val.intValue();
            }
        }

        return sort(tmp);
    }

    private static int[] sort(int[] arr) {

        if(arr.length <= 1) {
            return arr;
        }

        int pivotIdx = random.nextInt(arr.length - 1);

        List<Integer> less = new ArrayList<Integer>();
        List<Integer> greater = new ArrayList<Integer>();

        int pivotVal = arr[pivotIdx];

        for (int i = 0; i < arr.length; i++) {
            if(i == pivotIdx) {
                // Skip
            } else if (arr[i] < pivotVal) {
                less.add(arr[i]);
            } else if (arr[i] >= pivotVal) {
                greater.add(arr[i]);
            }
        }

        System.out.println("pivot["+ pivotIdx + "] = " + pivotVal + " from " + Arrays.toString(arr));
        System.out.println("lesser: " + less);
        System.out.println("greater: " + greater);

        return smushTogether(sort(less), pivotVal, sort(greater));

    }

    private static int[] smushTogether(int[] less, int pivotVal, int[] greater){

        System.out.println(String.format("smushing together: %s, %s, %s",
                           Arrays.toString(less), Integer.toString(pivotVal), Arrays.toString(greater)));

        int resultLen = less.length + greater.length + 1;
        int[] result = new int[resultLen];

        System.arraycopy(less, 0, result, 0, less.length);

        result[less.length] = pivotVal;

        System.arraycopy(greater, 0, result, less.length + 1, greater.length);

        return result;

    }

}