Weird implementation of quicksort
Let us start with the subroutine PARTITION. The loop maintains the following invariant:


  $A[k] \geq x$ for all $k \geq j$, and $A[k] \leq x$ for all $k \leq i$.


If the loop ever terminates, then the two ranges "$k \geq j$" and "$k \leq i$" cover the entire array, and in particular, $A[k] \leq x$ for all $k \leq j$, and $A[k] \geq x$ for all $k \geq i \geq j$. In particular, if $k \leq j$ and $\ell &gt; j$ then $A[k] \leq A[\ell]$. This is what PARTITION promises:


  If PARTITION$(A,p,r)$ returns $q$, then $x \leq y$ for all $x \in A[p],\ldots,A[q]$ and $y \in A[q+1],\ldots,A[r]$.


Furthermore, the particular choice $x=A[p]$ guarantees that PARTITION terminates &mdash; I'll let you work out this detail yourself.

This promise given by PARTITION guarantees the correctness of QUICKSORT: PARTITION partitions the array into two halves such that in the sorted array, all elements in the first half precede all those in the second half. In order to complete the sort, it remains to sort each half separately.

What might be throwing you off is a different variant of quicksort, in which PARTITION gives a stronger promise: all elements in $A[p],\ldots,A[q-1]$ are at most the pivot $A[q]$, and all elements in $A[q+1],\ldots,A[r]$ are at least the pivot $A[q]$. The version you describe doesn't have this promise, but otherwise is very similar to the version that you are familiar with.