Merge Sort

Introduction

We have see the brute force approach already. How can we speed things up? Think of the outer loop from iterating through the array to only the height of the tree.

Question (LC.464)

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Analysis

Why this thing is not in-place? The merge process has to be implemented with an extra array.

the base case - only one element we just return it

divide each array into two subarrays (what if the number is odd? does mid+1 handle it?)

we conquer left and right subarray by calling mergeSort on it

we use a merge function to combine the sorted results. merge two sorted arrays remember?

Code

public void sortArray(int[] A) {
    if (A == null || A.length == 0)
        return;
    // we want to create the temp here instead of in mergeSort 
    // cause then we have to do it everytime we call merge sort
    int[] temp = new int[A.length];
    mergeSort(A, temp, 0, A.length - 1);
}

private void mergeSort(int[] A, int[] temp, int start, int end) {
    // base case
    // only one element, just return it
    if (start == end) {
        return;
    }
    // divide
    // we want to divide the array into two havles
    // the left half is A[start...mid]] the right half is A[mid+1...end]
    int midpoint = (start + end) / 2;
    // conquer
    mergeSort(A, temp, start, midpoint);
    mergeSort(A, temp, midpoint + 1, end);
    // combine
    merge(A, temp, start, midpoint, end);
}

private void merge(int[] A, int[] temp, int start, int midpoint, int end) {
    int leftPointer = start;
    int rightPointer = midpoint + 1;
    // merge until the shorter one is finished
    int i = leftPointer;
    while (leftPointer <= midpoint && rightPointer <= end) {
        if (A[leftPointer] < A[rightPointer]) {
            temp[i++] = A[leftPointer++];
        } else {
            temp[i++] = A[rightPointer++];
        }
    }
    // if left array has leftovers
    while (leftPointer <= midpoint) {
        temp[i++] = A[leftPointer++];
    }
    // else if the right array has leftovers
    while (rightPointer <= end) {
        temp[i++] = A[rightPointer++];
    }
    // at the end, we have to put the temp info back to the actual array
    for (int a = start; a <= end; a++) {
        A[a] = temp[a];
    }
}

Conclusion

The recurrence is T(n) = 2T(n/2) + n. Merge sort is undoubtably fast with its O(nlogn) runtime. But it does require an extra O(n) space for its merging step. Next up, we will introduce another sorting algorithm with average O(nlogn) time and O(1) space. Stay tuned.

References

UMD CS251 Lecture 6 by David Mount