מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מיזוג מערכים/שאלה

להלן הפונקציה Merge המקבלת שני מערכים ממויינים:

# Merge. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )
	
2	l = r = m = 1
	
3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6		else if l > Length(L)
7			Merged[m++] = R[r++]
8		else if L[l] < R[r]
9			Merged[m++] = L[l++]
10		else
11			Merged[m++] = R[r++]

12	return Merged

אנא הוכח שהפונקציה מחזירה מערך ממויין המכיל את איחוד ערכי מערכי הכניסה, ונתח את סיבוכיות הפונקציה.