Sorting multiple columns of a matrix

Let $$A \in \mathbb{R}^{n \times k}$$ be a matrix where each column contains all of the numbers from $$\{1,\dots,n\}$$ in some arbitrary order. For example, if $$n=3, k=2$$, we could have $$A = \begin{pmatrix} 1 & 3 \\ 3 & 1 \\ 2 & 2 \\ \end{pmatrix}$$ I am now allowed to permute rows of $$A$$ with the goal of making the entries of the new matrix $$A'$$ as ''monotone'' as possible in each column. By that I mean that if I were to interpolate between the points of each column vector, the slope of the interpolating function would change sign as seldom as possible for each. Formally, we could minimize $$L(A') = \sum_{i=1}^{k} \sum_{j=3}^{n} 1 \Big(sign(A'_{i,j} - A'_{i,j-1}) \neq sign(A'_{i,j-1} - A'_{i,j-2}) \Big)$$ I am now interested in how bad this may be depending on $$n$$ and $$k$$. Obviously, for $$k=1$$ we can get $$L=0$$ by simply sorting the only column.

Is there a better way to look at this problem and does it perhaps have an official name? I would like to learn more about worst case bounds.