merge sort merge run time anaylsis

I have some confusion of the run time analysis of the merge function in merge sort.

Merg(A,p,q,r)
1 n1=q-p+1
2 n2=r-q
3 let L[1..n1+1] and R[1..n2+1] be new arrays
4 for i=1 to n1
5     L[i] = A[p+i-1]
6 for j =1 to n2
7    R[j] = A[q+j]
8  L[n1+1] = infinity
9 R[n2+1] = infinity
10 i =0
11 j=0
12 for k=p to r
13   if L[i]<=R[j]
14       A[k]=L[i]
15       i=i+1
16    else A[k] = R[j]
17       j=j+1

In my book it says the following: to see that the merge procedure runs in O(n) time, where n=r-p+1, observe that each of lines 1-3 and 8-11 takes constant time, the for loops of lines 4-7 take O(n1+n2) = O(n)time, and there are n iterations of the for oop of lines 12-17, each of which takes constant time

My question is why do lines 12-17 take constant time per iteration and not affect the run time but lines 4-7 don't take constant time. to me, it seems like both loops are doing the same thing. can someone help clarify开发者_Python百科 this for me? Thanks!

It's confusingly written. Both loops (4-7 and 12-17) have the same length (n) and the inside of both loops are constant time (no nested loops). So they're each O(n), for a total of O(n) for the whole routine.

Regarding Jerry's answer, lines 4-7 matter because they're still O(n). If you could magically remove lines 12-17 you'd still have an O(n) routine.

Lines 1 through 9 are just splitting the input (A) into two pieces (L and R). Lines 10 and 11 are doing a bit of initializing to get ready for merging. The merge itself is from lines 12-17.

IOW, everything before line 12 (or arguably 10, not that it really matters) is irrelevant to analyzing the merge because none of it is really part of the merge at all.

Edit: Ultimately, however, a single iteration from 1 to 27 is linear: in lines 4-7, you walk exactly once through the input array, assigning each input exactly once to either L or R. In lines 12-27, you then walk through those two pieces, and copy them back to the original input. Ignoring a few other minor details like initializing i and j, the total number of operations is exactly 2N. For big-O notation, constant factors are ignored, so it's O(N).