0-Sorting

1. Heapsort
2. Mergesort
3. Quicksort

1-Heapsort.java

public static void heapSort(int[] heap){
    for(int i = heap.length / 2 - 1; i >= 0; i--){
        percDown(heap, i, a.length - 1);
    }
    for(int i = heap.length - 1; i > 0; i--){
        swap(heap, 0, i);
        percDown(heap, 0, i - 1);
    }
}

public static void percDown(int[] heap, int position, int end){
    int temp = heap[position];
    int next;
    for(;(next = leftSon(position)) <= end; position = next){
        if(next != end && heap[next] < heap[next + 1]) next++;
        if(heap[position] < heap[next]) heap[position] = heap[next];
        else break;
    }
    heap[position] = temp;
}

public static int leftSon(int parent){
    return parent * 2 + 1;
}

2-MergeSort.java

public static void mergeSort(int[] input){
    int[] temp = new int[input.length];
    mergeSort(0, input.length - 1, input, temp);
}
public static void mergeSort(int begin, int end, int[] input, int[] temp){
    if(begin <= end) return;
    int mid = (begin + end) / 2;
    mergeSort(begin, mid, input, temp);
    mergeSort(mid + 1, end, input, temp);
    
    int left = begin;
    int right = mid + 1;
    int current = begin;
    while(left <= mid && right <= end){
        if(input[left] < input[right]) temp[current++] = input[left++];
        else temp[current++] = input[right++];
    }
    while(left <= mid) temp[current++] = input[left++];
    while(right <= end) temp[current++] = input[right++];
    for(int i = begin; i <= end; i++){
        input[i] = temp[i];
    }
}

3-Quicksort.java

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

public static void quickSort(int[] input, int begin, int end){
    if(end - begin <= CUTOFF){
        insertionSort(a, left, right);
        return;
    }
    int axis = median3(input, begin, end);
    int left = begin;
    int right = end - 1;
    while(true){
        while(input[++left] < axis);
        while(input[--right] > axis);
        if(left < right) swap(input, left, right);
        else break;
    }
    swap(input, left, end - 1);
    quickSort(input, begin, mid - 1);
    quickSort(input, mid + 1, end);
}

public static int median3(int[] input, int begin, int end){
    int mid = (begin + end) / 2;
    if(input[mid] < input[begin]) swap(input, mid, begin);
    if(input[end] < input[begin]) swap(input, end, begin);
    if(input[end] < input[mid]) swap(input, end, mid);
    swap(input, mid, end - 1);
    return a[end - 1];
}

public static void insertionSort(int[] input){
    for(int i = 1; i < input.length; i++){
        int temp = input[i];
        int j = i;
        for(; j > 0 && temp < input[j - 1]; j--) input[j] = input[j - 1];
        input[j] = temp;
    }
}