7. Merge Sort

Merge sort is a recursive algorithm that splits the array in half until there is one element left, then it starts combining the subarrays together until it completely sorted. Java uses this sorting algorithm with its Collections.

public <T extends Comparable<? super T>> void mergeSort(T[] array) {
    mergeSortHelper(array, array.length);
}

private <T extends Comparable<? super T>> void mergeSortHelper(T[] array, int n) {
    if (n < 2) {
        return;
    }

    int middle = n / 2;
    T[] leftPortion = (T[]) new Object[middle];
    T[] rightPortion = (T[]) new Object[n - middle];

    for (int i = 0; i < middle; i++) {
        leftPortion[i] = array[i];
    }
    for (int i = middle; i < n; i++) {
        rightPortion[i - middle] = array[i];
    }

    mergeSortHelper(leftPortion, middle);
    mergeSortHelper(rightPortion, n - middle);

    merge(array, leftPortion, rightPortion, middle, n - middle);
}

private <T extends Comparable<? super T>> void merge(T[] array, T[] leftPortion, T[] rightPortion, int left, int right) {
    int i = 0; // leftPortion
    int j = 0; // rightPortion
    int k = 0;
    while (i < left && j < right) {
        if (leftPortion[i].compareTo(rightPortion[j]) <= 0) {
            array[k++] = leftPortion[i++];
        } else {
            array[k++] = rightPortion[i++];
        }
    }

    while (i < left) {
        array[k++] = leftPortion[i++];
    }

    while (j < right) {
        array[k++] = rightPortion[j++];
    }
}

Merge sort has a time complexity of $O(nlog(n))$ which is decent for sorting! However, remember the trade of time and space complexities? Well, merge sort does have a space complexity of $O(n)$ which is something to consider.

Can we do better with comparison-based sorting, which the previous five sorting algorithms have been based on?

No, since any comparison-based sorting algorithm performs at least $\Omega(nlog(n))$ comparisons on the worst case of input size $n$, merge sort is the best in terms of time complexity.

Can we do better with non-comparison based sort?

Yes but with restrictions.

Next Page →