public static <T extends Comparable<T>> void quickSortAverage(List<T>list) {
		Queue<int[]>q=new ArrayDeque<>(Arrays.asList(new int[]{0,list.size()}));
		while (!q.isEmpty()) {
			int[]r=q.poll();
			List<T>A=list.subList(r[0],r[1]);
			if (A.size()<=1) continue;
			int p=A.size()/2,l=1; T pivot=A.get(p-1);
			Collections.swap(A,0,p-1);
			for (int i=1;i<A.size();++i) if(A.get(i).compareTo(pivot)<=0) Collections.swap(A,l++,i);
			Collections.swap(A,0,l-1);
			q.offer(new int[]{r[0],r[0]+l-1});
			q.offer(new int[]{r[0]+l,r[1]});
		}
	}