Merge Sort & Quick Sort (JAVA)

Merge Sort

- best : $\ O(n \log{n})$

- avg : $\ O(n \log{n})$

- worst : $\ O(n \log{n})$

- out-of-place

- stable

public static void mergeSort(int[] arr, int low, int high) {
    if (high-low < 1)
        return;

    int mid = (low+high)/2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid+1, high);

    int[] tmp = new int[high-low+1];
    int i = low, j = mid+1, idx = 0;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j])
            tmp[idx++] = arr[i++];
        else
            tmp[idx++] = arr[j++];
    }
    while (i <= mid)
        tmp[idx++] = arr[i++];
    while (j <= high)
        tmp[idx++] = arr[j++];

    for (int k = 0; k < tmp.length; k++)
        arr[low + k] = tmp[k];
}

 

Quick Sort

- best : $\ O(n \log{n})$

- avg : $\ O(n \log{n})$

- worst : $O(n^2)$

- in-place 

- unstable

public static void swap(int[] arr, int from, int to) {
    int tmp = arr[from];
    arr[from] = arr[to];
    arr[to] = tmp;
}

public static void quickSort(int[] arr, int low, int high) {
    if (high-low < 1)
        return;

    int pivot = high;
    int i = low; // the first index s.t. arr[idx] > arr[pivot]

    for (int j = low; j < high; j++) {
        if (arr[j] <= arr[pivot])
            swap(arr, i++, j);
    }

    swap(arr, i, pivot);
    quickSort(arr, low, i-1);
    quickSort(arr, i+1, high);
}