Merging (6)
Analysis (counting comparisons):
Let n1 and n2 be the lengths of a1 and a2.Let n = n1 + n2.Assume that steps 2.1–2 perform a single comparison.
Steps 2.1–2 are repeated at most n–1 times.
Max. no. of comparisons = n – 1
Time complexity is again O(n).