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 intoLwith elements - the subarray
A[q+1..n]is copied intoRwith elements - both
LandRare 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]andR[j]intoA[r]and advance that index (use<=so equal values fromLgo 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 + 1Cost
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.