Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Goal

Merge takes two sorted arrays of nearly equal length and produces one sorted array. It is the "combine" step of mergesort.

Set-up for merge(A, p, q, n):

  • the subarray A[p..q] is copied into L with elements
  • the subarray A[q+1..n] is copied into R with elements
  • both L and R are sorted in non-decreasing order
  • the merged result overwrites A[p..n]

Idea

Keep an index i into L, j into R and r into A. Since both arrays are sorted, the smallest remaining value is always either L[i] or R[j]:

  • copy the smaller of L[i] and R[j] into A[r] and advance that index (use <= so equal values from L go first, which keeps the sort stable)
  • continue while both arrays still have elements
  • when one array runs out, copy the rest of the other array straight into A

Example: L = [10, 20, 36], R = [12, 14, 30, 40, 44]. The output grows as ; then L is empty and are copied, giving [10, 12, 14, 20, 30, 36, 40, 44].

Code

def merge(A, p, q, n):
    a = q - p + 1                  # size of left part
    b = n - q                      # size of right part
    L = [A[p + k] for k in range(a)]
    R = [A[q + 1 + k] for k in range(b)]
    i = j = 0
    r = p
    while i < a and j < b:         # copy the smaller value
        if L[i] <= R[j]:
            A[r] = L[i]
            i = i + 1
        else:
            A[r] = R[j]
            j = j + 1
        r = r + 1
    while i < a:                   # remainder of L, if any
        A[r] = L[i]
        i = i + 1
        r = r + 1
    while j < b:                   # remainder of R, if any
        A[r] = R[j]
        j = j + 1
        r = r + 1

Cost

Every element is copied out once and back once, so merging elements takes time. It also needs extra memory for L and R, which is why mergesort is not in place.