Why is subarray $A[p..k-1]$ empty when $k=p$?
It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j &lt; i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j &lt; i$. In yet other cases, we do not want to allow empty arrays, and then $A[i..i-1]$ is undefined as well.

Since these conventions are not standard (indeed, they are conflicting), if one of them is used, it should be announced beforehand, or when it occurs.