Sort

public static void qsort(int[] arr){
	qsort(arr, 0, arr.length - 1);
}

public static void qsort(int[] arr, int start, int end){
	if(end - start < 1)
		return;
	int pivot = arr[start], i = start, j = end;
	while(i < j){
		for(;j>i && arr[j] >= pivot; --j);
		arr[i] = arr[j];
		for(;i<j && arr[i] <= pivot; ++i);
		arr[j] = arr[i];
	}
	arr[i] = pivot;
	qsort(arr, start, i - 1);
	qsort(arr, i + 1, end);
}

public static void mergeSort(int[] arr){
	int[] tmp = new int[arr.length];
	mergeSort(arr, 0, arr.length, tmp);
}

static void mergeSort(int[] arr, int start, int end, int[] tmp){
	if(end - start < 2)
		return;
	int mid = (start + end) >> 1;
	mergeSort(arr, start, mid, tmp);
	mergeSort(arr, mid, end, tmp);
	merge(arr, start, mid, end, tmp);
}

static void merge(int[] arr, int start, int mid, int end, int[] tmp){
	int i = start, j = mid, k = start;
	while(i<mid && j<end)
		tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
	while(i<mid)
		tmp[k++] = arr[i++];
	while(j<end)
		tmp[k++] = arr[j++];
	System.arraycopy(tmp, start, arr, start, end - start);
}

static int[] shellSeq = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,
        16001, 36289, 64769, 146305, 260609, 587521, 1045505, 2354689, 4188161,
        9427969, 16764929, 37730305, 67084289, 150958081, 268386305, 603906049, 1073643521};
public static void shellSort(int[] arr) {
    int n = arr.length, k = 0;
    for(; k < shellSeq.length && shellSeq[k] < n; ++k);
    -- k;
    for(; k>=0; --k) {
        int p = shellSeq[k];
        for(int i=p; i<n; ++i) {
            int q = arr[i], j = i - p;
            for(; j>=0 && arr[j] > q; j-=p) {
                arr[j+p] = arr[j];
            }
            arr[j+p] = q;
        }
    }
}