Merge Sort

This is probably one of the sorting algorithms that I have a lot of difficulty understanding, alongside Quick Sort.

This algorithm takes more space, so it’s a tradeoff. It’s a Divide and Conquer algorithm. High Level Idea:

1. Divide array in half
2. Sort each half recursively following the same algorithm
3. Merge the results

Time Complexity

• Worst Case: $O(n\log n)$
• Average Case: $O(n\log n)$
• Best Case: $O(n)$

Space Complexity

• Worst Case: $O(1)$

Merge Sort Pseudocode

We can logically divide without physically dividing an array.

From Mari Programming class

def merge(temp, data, lo, mid, hi):
    '''Merge step for merge sort.'''
    temp[lo:hi] = data[lo:hi] # Copy.
    i = lo  # start of lower sublist.
    j = mid # start of upper sublist.
    k = lo  # start of merged list.
    while k < hi:
        if i >= mid:  # lower sublist finished?
            data[k] = temp[j]; j += 1
        elif j >= hi: # upper sublist finished?
            data[k] = temp[i]; i += 1
        elif temp[i] < temp[j]:
            data[k] = temp[i]; i += 1
        else:
            data[k] = temp[j]; j += 1
        k += 1
 
def split(temp, data, lo, hi):
    '''The splitting stages of mergesort.'''
    if hi - lo >= 2:
        mid = (lo + hi) // 2
        split(temp, data, lo, mid)
        split(temp, data, mid, hi)
        merge(temp, data, lo, mid, hi)
        
def mergesort(ls):
    '''Standard mergesort.'''
    tmp = [0] * len(ls)         # Temporary storage
    split(tmp, ls, 0, len(ls))

Bottom up merge sort

def mergesort_bu(ls):
    '''Bottom-up mergesort.'''
    n = len(ls)
    temp = [0] * n      # Temporary storage
    sz = 1              # Sublist size for merges.
    while sz < n:
        lo = 0
        sz2 = sz + sz   # sz2 = 2*sz
        while lo < n - sz:
            hi = min(lo + sz2, n)
            merge(temp, ls, lo, lo + sz, hi)
            lo += sz2
        sz = sz2

CS240