public static <T extends Comparable<T>> void  sort(int i, int j, List <T> s){
		if(i >= j)
			return;
		int rand = (i + j) / 2;
		T tmp = s.get(rand);
		s.set(rand, s.get(j));
		s.set(j,  tmp);
		T cmp = s.get(j);
		int st = i;
		int ed = j;
		while(true){
			while(st < ed && s.get(st).compareTo(cmp) <= 0)st++;
			while(st < ed && s.get(ed).compareTo(cmp) >= 0)ed--;
			if(st < ed){
				T a = s.get(st);
				s.set(st, s.get(ed));
				s.set(ed, a);
			}
			else
				break;
			st++;
			ed--;
		}
		T a = s.get(st);
		s.set(st, s.get(j));
		s.set(j, a);
		sort(i, st - 1, s);
		sort(st + 1, j, s);
	}