# How to understand out of bound in the following theoretical context?

Consider the following initialization step of loop invariant for merge procedure

Initialization: Prior to the first iteration of the loop, we have $$k=p$$, so that the subarray $$A[p .. k - 1]$$ is empty. This empty subarray contains the k- p= 0 smallest elements of $$L$$ and $$R$$, and since $$i = j = 1$$, both $$L[i]$$ and $$R[j]$$ are the smallest elements of their arrays that have not been copied back into $$A$$.

I have doubt in the above statement that if $$k=p$$, then array $$A[p..p-1]$$ is impossible and hence the further argument cannot proceed, which didn't happen. Where am I going wrong?

• There’s nothing wrong with empty subarrays, especially if they have length exactly zero. – Yuval Filmus Jan 19 at 12:56

It is often useful to allow arrays of zero length. These are just empty arrays. The length of the subarray $$A[i\ldots j]$$ is $$j-i+1$$, so when $$j=i-1$$, we just get an array of length 0.
• An array $$A[1\ldots n]$$ can always be partitioned into two arrays $$A[1\ldots i]$$ and $$A[i+1 \ldots n]$$ of lengths $$i,n-i$$. This works even for $$i \in \{0,n\}$$.
• We can construct an array $$A[1\ldots n]$$ inductively using the formula $$A[1\ldots i] = A[1\ldots (i-1)] \cdot A[i]$$. The base case is the empty array $$A[1\ldots 0]$$.
Having arrays of negative length makes less sense, and could lead to confusion and errors, since there is no semantics under which the formula $$|A[i\ldots j]| = j-i+1$$ would hold for them, since array lengths are non-negative.