1
$\begingroup$

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?

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

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.

Why is this useful? Here are some examples:

  • 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.