I'm trying to understand the left-looking LU factorization algorithm for sparse matrices, by reading T.A. Davis' book, and have trouble in one step (sorry for the specific question) about returning sorted vectors.

The algorithm `cs_lu`

is supposed to return a CSC matrix, i.e. compressed, sorted columns. There is a routine `cs_spsolve`

that solves a linear system $L x=b$ for a lower-triangular matrix $L$ and a compressed column vector $b$; however, the result $x$ is not returned as a sorted vector, but only "topologically sorted", namely the nonzero entries $x_i$ only satisfy the guarantee that $x_i$ is after $x_j$ if there is a path $L_{i,i_1},L_{i_1,i_2},\dots,L_{i_n,j}$ of nonzeros in $L$.

Still, this vector $x$ is used directly as a new column of the result. My question: how can one guarantee that the columns of the result $L$ are sorted, without actually sorting them? Why is the code (Section 6.2, page 87) even correct? [To clarify: I'm sure it's correct, I just don't see why...]

Many thanks!