javaでクイックソート 効率はよくない

QuickSort.java

package jp.dip.sys1.yagi.sort;

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

public class QuickSort {
    /**
     * クイックソートやで
     * @param list ソート対象のリスト
     * @param comp 比較関数
     * @return ソート済みのリスト
     */
    public static <T> List<T> sort(List<T> list, Comparator<T> comp) {
        if(list.isEmpty()){
            return list;
        }
        //ピボットより値の小さいリスト
        List<T> smaller = new ArrayList<T>();
        //ピボットより値の大きいリスト
        List<T> greater = new ArrayList<T>();
        Random p = new Random(System.currentTimeMillis());
        //ピボット
        int index = p.nextInt(list.size());
        T pv = list.get(index);
        
        //ピボットより小さい値、大きい値で各リストに振り分ける
        for (int i = 0; i < list.size(); i++) {
            if (i != index) {
                T l = list.get(i);
                if (comp.compare(pv, l) >= 0) {
                    smaller.add(l);
                } else {
                    greater.add(l);
                }
            }
        }
        //ピボットより値の小さいリスト、ピボットより値の大きいリストをそれぞれクイックソートにかける
        //ピボットを真ん中にして連結して返す
        List<T> result = new ArrayList<T>();
        result.addAll(QuickSort.sort(smaller, comp));
        result.add(pv);
        result.addAll(QuickSort.sort(greater, comp));
        return result;
    }
    //sample
    public static void main(String[] args) {
        Integer[] l = new Integer[] { 1, 20, 4205, 539, 5, 2, 104, 100, 6, 1, 7, 239, 2, 55 };
        List<Integer> list = Arrays.asList(l);
        list = QuickSort.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (Integer r : list) {
            System.out.println(r);
        }
    }

}