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.

Example

I: [3, 2, 1, 4, 5] 
O:
start: 0 end: 4 slide: [3, 2, 1, 4, 5]
start: 0 end: 2 slide: [3, 2, 1]
start: 0 end: 1 slide: [3, 2]
start: 0 end: 0 slide: [3]
start: 1 end: 1 slide: [2]
merged: [2, 3]
start: 2 end: 2 slide: [1]
merged: [1, 2, 3]
start: 3 end: 4 slide: [4, 5]
start: 3 end: 3 slide: [4]
start: 4 end: 4 slide: [5]
merged: [4, 5]
merged: [1, 2, 3, 4, 5]

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 w/ temp array

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];
    }
}

Code w/ new slice

Programs with side effects, such as modifying a shared temp array, cannot be easily parallelized because mutual exclusion has to be involved.

def sortIntegers2(self, A: List[int]) -> None:
    
    n = len(A)
    
    if n == 0:
        return 

    sorted_list = merge_sort(A, 0, n-1)
    for i in range(n):
        A[i] = sorted_list[i]

    return 


def merge_sort(A: List[int], start: int, end: int) -> List[int]:
    # print(f'start: {start} end: {end} slide: {A[start:end+1]}')
    # base 
    if start == end:
        return [A[start]]

    # divide 
    mid = (start + end) // 2 

    # conquer 
    left_arr = merge_sort(A, start, mid)
    right_arr = merge_sort(A, mid+1, end)

    # merge 
    merged = merge(left_arr, right_arr)
    return merged

def merge(left_arr: List[int], right_arr: List[int]) -> List[int]:

    result = [] 

    i = 0 
    j = 0 

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    
    if i < len(left_arr):
        result.extend(left_arr[i:])

    if j < len(right_arr):
        result.extend(right_arr[j:])

    return result 
    

Concurrent Code

In practice, the concurrent code will not run faster by default. There is a cost (overhead to create a goroutine, go scheduler to schedule the goroutine, gc to terminate the goroutine, etc) associated with making the run concurrent. The break even point is around 1000 elements from this blog post.

func sortIntegers2 (A *[]int)  {

    if A == nil || len(*A) <= 1 {
        return
    }

    inputList := *A

    n := len(inputList)

    ch := make(chan []int)

    go mergeSort(inputList, ch)

    sortedList := <- ch

    for i := 0; i < n; i++ {
        inputList[i] = sortedList[i]
    }

    return
}



func mergeSort (list []int, ch chan []int) {

    n := len(list)

    if n == 1 {
        ch <- list
        return
    }


    // divide
    mid := n / 2

    leftCh := make(chan []int)
    rightCh := make(chan []int)

    // conquer
    go mergeSort(list[:mid], leftCh)
    go mergeSort(list[mid:], rightCh)

    // merge
    leftList := <- leftCh
    rightList := <- rightCh

    close(leftCh)
    close(rightCh)
    ch <- merge(leftList, rightList)
}


func merge (leftList []int, rightList []int) []int {
    result := []int{}

    i := 0
    j := 0

    for i < len(leftList) && j < len(rightList) {

        if leftList[i] <= rightList[j] {
            result = append(result, leftList[i])
            i++
        } else {
            result = append(result, rightList[j])
            j++
        }

    }

    if i < len(leftList) {
        result = append(result, leftList[i:]...)
    }

    if j < len(rightList) {
        result = append(result, rightList[j:]...)
    }

    return result
}

Conclusion

The recurrence is T(n) = 2T(n/2) + n.

Merge sort recursion tree

Merge sort time complexity

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

• Medium - Parallel Merge Sort in Go

• Wikipedia - Timsort