Advanced Sort

Merge Sort

Think

• Divide and Conquer
• Recursion

Solution

public void mergeSort(int[] arr, int left, int right){
    if(left >= right)
        return;
    int mid = left + ((right - left) >> 1);
    mergeSort(arr, left, mid - 1);
    mergeSort(arr, mid, right);
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right){
    int[] newarr = new int[right - left + 1];

    for(int i = left; i <= right; i++)
        newarr[i - left] = arr[i];

    int l = 0;
    int r = mid - left + 1;
    for(int i = left; i <= right; i++){
        if(l > mid - left)
            arr[i] = newarr[r++];
        else if(r > right - left)
            arr[i] = newarr[l++];
        else
            arr[i] = newarr[l] < newarr[r]? newarr[l++] : newarr[r++];
    }
}

Quick Sort

Think

• Set pivot (the rear of array or ) and consider it as a standard
• Pass the array and make the element less than pivot on the pivot's left and the element larger than pivot on the pivot's right;

Solution

public void quickSort(int[] arr, int l, int r){
    if(l > r)
        return;

    int pivot = pivot(arr, l, r);
    quickSort(arr, l, pivot - 1);
    quickSort(arr, pivot + 1, r);
}


private int pivot(int[] arr, int l, int r){
    int pivot = arr[r];
    int idx = l;
    for(int i = l; i < r; i++){
        if(arr[i] < pivot){
            int tmp = arr[idx];
            arr[idx++] = arr[i];
            arr[i] = tmp;
        }
    }
    arr[r] = arr[idx];
    arr[idx] = pivot;
    return idx;
}