# Non-Messing-Up++: Diagonal Sorting and Young Tableaux _Date: 2026-03-13_ _Updated: 2026-03-18_ ___ I've been sitting on this for too long. Happened upon this idea while trying to figure out parallel sorting techniques, using SIMD "in-register" sorting as a primitive. Proof fleshed out by Opus 4.6 (and LaTeX-ified, which is important for making it look correct). I found Claude was pretty decent at poking holes in my reasoning, though it wasn't great at coming up with counterexamples. And hey, better to be open and wrong at this stage than to be closed. The decreasing form (Lemma 2) is not particularly interesting to me, because only the increasing form is needed for a parallel SIMD mergesort strategy :) # Anti-Diagonal Sort Preserves the Young Tableau Property ### Notes Why anti-diagonal instead of diagonal? I'm pretty sure that diagonal vs antidiagonal sorting would be symmetric in the following, just that I like things to start from the left if possible. I think there may be an issue with diagonal sorting in that regard, though Young Tableau obviously implies diagonals are already sorted with rows/cols. Of course, antidiagonal also just sounds cooler. The theorem below seems rather simple, so I'm a bit suspicious I didn't find it stated this way already. The closest neighbors I found are the classical non-messing-up theorem for row/column sorting and the products-of-two-chains literature, though I don't understand the latter well enough to know whether this is already hiding in it somewhere. Maybe I should call this thing "non-messing-up++"? Regardless, this was a fun little exercise in capturing some ideas more rigorously -- ideas which an algorithm will be predicated on. ## Conventions Throughout, $G$ is an $n \times n$ grid of distinct real numbers, indexed by $(r, c)$ for $r, c \in \{0, \ldots, n-1\}$, with $r$ increasing downward and $c$ increasing rightward. - **Rows** are sorted left to right: $G[r][c] < G[r][c+1]$ - **Columns** are sorted top to bottom: $G[r][c] < G[r+1][c]$ - **Anti-diagonal** $\mathcal{A}_d = \{(r, c) : r + c = d\}$, sorted bottom-left to top-right: within $\mathcal{A}_d$, the minimum is placed at the position with the smallest column index (largest row index), and values increase with column index. A grid satisfying the row and column conditions is a **[Young tableau](https://mathworld.wolfram.com/YoungTableau.html)**. ![[tableau-young-grid-dark.svg|700]] ## Theorem **Let $G$ be an $n \times n$ Young tableau with distinct entries. Sorting every anti-diagonal (bottom-left to top-right) produces a grid $G'$ that is again a Young tableau.** In other words, $G'$ has all three axes -- rows, columns, and anti-diagonals -- simultaneously sorted. ![[tableau-sorting-effect.svg|700]] --- ## Anti-Diagonal Structure Anti-diagonal $\mathcal{A}_d$ occupies columns $c_d^- \leq c \leq c_d^+$, where: $c_d^- = \max(0, d - n + 1), \qquad c_d^+ = \min(d, n - 1)$ Its length is $\ell_d = c_d^+ - c_d^- + 1$, which equals $d + 1$ for $d < n$ and $2n - 1 - d$ for $d \geq n$. After sorting $\mathcal{A}_d$, the element at column $c$ holds the order statistic of rank $c - c_d^-$ (0-indexed from the minimum). --- ## Proof Strategy Every row-adjacent or column-adjacent pair of positions $(r, c)$ and $(r, c+1)$ (or $(r, c)$ and $(r+1, c)$) lies on adjacent anti-diagonals $\mathcal{A}_d$ and $\mathcal{A}_{d+1}$. Therefore, it suffices to show that for every $d$, sorting both $\mathcal{A}_d$ and $\mathcal{A}_{d+1}$ preserves the row and column ordering between them. (Note: sorting all anti-diagonals simultaneously is safe because each anti-diagonal's elements are disjoint -- sorting $\mathcal{A}_{d+2}$ cannot affect any element on $\mathcal{A}_d$ or $\mathcal{A}_{d+1}$, so we can analyze each consecutive pair independently.) There are two regimes: - **Increasing side** ($d < n - 1$): $\ell_d < \ell_{d+1}$, i.e., $\mathcal{A}_{d+1}$ is longer by one. - **Decreasing side** ($d \geq n - 1$): $\ell_d > \ell_{d+1}$, i.e., $\mathcal{A}_d$ is longer by one. Each regime requires its own lemma. The underlying structure is the same, but the decreasing form is most cleanly obtained by mirroring the increasing one. --- ## Domination Relationships from the Young Tableau Before stating the lemmas, we need to know what the Young tableau gives us about elements on adjacent anti-diagonals. The local pattern depends on which side of the diamond we are on. **Increasing side.** Suppose $d < n - 1$, so $\mathcal{A}_{d+1}$ is longer by one. Over the shared column range, positions $(d - c, c)$ on $\mathcal{A}_d$ and $(d + 1 - c, c)$ on $\mathcal{A}_{d+1}$ share the same column, so column-sortedness gives $\mathcal{A}_d[c] < \mathcal{A}_{d+1}[c].$ Also, positions $(d - c, c)$ on $\mathcal{A}_d$ and $(d - c, c + 1)$ on $\mathcal{A}_{d+1}$ share the same row, so row-sortedness gives $\mathcal{A}_d[c] < \mathcal{A}_{d+1}[c+1].$ So on the increasing side, each element of the shorter anti-diagonal is less than two neighboring elements of the longer one: $A_j < B_j \qquad \text{and} \qquad A_j < B_{j+1}.$ **Decreasing side.** Suppose $d \geq n - 1$, so $\mathcal{A}_d$ is longer by one. Let $c_0 = c_d^-$ be the leftmost column of $\mathcal{A}_d$, and reindex by $A_j = \mathcal{A}_d[c_0 + j], \qquad B_j = \mathcal{A}_{d+1}[c_0 + 1 + j].$ Now for each shared column $c = c_0 + 1 + j$, column-sortedness gives $A_{j+1} < B_j,$ and row-sortedness gives $A_j < B_j.$ So on the decreasing side, each element of the shorter anti-diagonal sits above two neighboring elements of the longer one: $A_j < B_j \qquad \text{and} \qquad A_{j+1} < B_j.$ This **double domination** is the key structure. In a standard row-sort or column-sort, you only get single domination ($A_j < B_j$), and the classical rearrangement lemma handles that. But adjacent anti-diagonals differ in length by one, which breaks the classical equal-length argument. The second domination is exactly what compensates for the length mismatch. ![[tableau-double-domination.png]] --- ## Key Lemma: Double Domination Rank Inequality ### Increasing Form > **Lemma 1.** Let $A = (A_0, \ldots, A_{m-1})$ and $B = (B_0, \ldots, B_m)$ be sequences of distinct reals satisfying, for all $j = 0, \ldots, m - 1$: > > $A_j < B_j \qquad \text{and} \qquad A_j < B_{j+1}$ > > Then $\operatorname{sorted}(A)_k < \operatorname{sorted}(B)_k$ for all $k = 0, \ldots, m - 1$. ### Decreasing Form > **Lemma 2.** Let $A = (A_0, \ldots, A_m)$ and $B = (B_0, \ldots, B_{m-1})$ be sequences of distinct reals satisfying, for all $j = 0, \ldots, m - 1$: > > $A_j < B_j \qquad \text{and} \qquad A_{j+1} < B_j$ > > Then $\operatorname{sorted}(A)_{k+1} < \operatorname{sorted}(B)_k$ for all $k = 0, \ldots, m - 1$. ### Proof of Lemma 1 > NOTE: However, if I'm being frank, I don't love the counting argument argument below for something that feels like it should be more obvious (but thanks, Claude). See [[#Appendix another sketch]] for a more-inductive though less-formal argument. Fix $k \in \{0, \ldots, m-1\}$. We want to show $\operatorname{sorted}(A)_k < \operatorname{sorted}(B)_k$. Let $b = \operatorname{sorted}(B)_k$ -- the $(k+1)$-st smallest element of $B$. Our target is to show that at least $k+1$ elements of $A$ are strictly less than $b$; if so, then $\operatorname{sorted}(A)_k$ (the $(k+1)$-st smallest of $A$) must be less than $b$. Let $S = \{j \in \{0, \ldots, m\} : B_j \leq b\}$ be the indices of $B$ that are at most $b$. Since $b$ is the $(k+1)$-st smallest element of $B$, we have $|S| \geq k + 1$. Let $T = \{i \in \{0, \ldots, m-1\} : A_i < b\}$ be the "good" indices of $A$ -- positions where $A_i$ is already below our target. The complement $U = \{0, \ldots, m-1\} \setminus T$ collects the "bad" indices: positions where $A_i \geq b$, working against us. Our goal is to show there aren't too many bad indices, i.e. $|U| \leq m - k - 1$, which gives $|T| \geq k + 1$. The double domination lets us turn each bad index into constraints on $B$. For any $i \in U$, we have $A_i \geq b$. Since $A_i < B_i$, this forces $B_i > b$, so $i \notin S$. Since $A_i < B_{i+1}$, this forces $B_{i+1} > b$, so $i + 1 \notin S$. In other words, each bad index $i$ "poisons" two consecutive positions in $B$: both $i$ and $i+1$ are excluded from $S$. More precisely, $U \subseteq S^c$ (complement of $S$) and $U + 1 \subseteq S^c$, where $S^c = \{0, \ldots, m\} \setminus S$ and $U + 1 = \{i + 1 : i \in U\}$. **Counting argument.** The poisoned positions are $U \cup (U + 1) \subseteq S^c$. But consecutive bad indices share a victim -- if both $i$ and $i+1$ are bad, they both poison position $i+1$. Still, this overlap isn't perfect: the smallest bad index $\min(U)$ poisons $\min(U)$ itself, but $\min(U) \notin U + 1$ (since $\min(U) - 1 \notin U$). So $\min(U)$ is a poisoned position that only the first bad index contributes. This gives $|U \cup (U+1)| \geq |U| + 1$. Since $U \cup (U+1) \subseteq S^c$: $|U| + 1 \leq |S^c| = (m + 1) - |S| \leq m - k$ Hence $|U| \leq m - k - 1$ and $|T| = m - |U| \geq k + 1$. (If $U = \emptyset$, then $|T| = m \geq k + 1$ trivially.) $\square$ ![[tableau-lemma1.png]] ### Proof of Lemma 2 Note: I did check Lemma 1 rigorously. Lemma 2 is here mostly for symmetry, and I have not pressure-tested it to the same level because the later mergesort only needs the increasing form. So yes, this part is still a little bit meta-proof-by-prayer ;) More seriously: this is just Lemma 1 seen in a mirror. Define $X_j = -B_{m-1-j} \qquad (0 \leq j \leq m-1),$ and $Y_j = -A_{m-j} \qquad (0 \leq j \leq m).$ For each $j = 0, \ldots, m-1$, the hypotheses of Lemma 2 give $A_{m-1-j} < B_{m-1-j} \qquad \text{and} \qquad A_{m-j} < B_{m-1-j}.$ After negating, this becomes $X_j < Y_{j+1} \qquad \text{and} \qquad X_j < Y_j.$ So $X$ and $Y$ satisfy the hypotheses of Lemma 1. Therefore $\operatorname{sorted}(X)_k < \operatorname{sorted}(Y)_k \qquad \text{for } k = 0, \ldots, m-1.$ Now sorting a negated sequence reverses the order statistics, so $\operatorname{sorted}(X)_k = -\operatorname{sorted}(B)_{m-1-k}, \qquad \operatorname{sorted}(Y)_k = -\operatorname{sorted}(A)_{m-k}.$ Hence $\operatorname{sorted}(A)_{m-k} < \operatorname{sorted}(B)_{m-1-k}.$ Renaming $t = m - 1 - k$ gives $\operatorname{sorted}(A)_{t+1} < \operatorname{sorted}(B)_t,$ which is exactly the conclusion of Lemma 2. $\square$ --- ## Proof of the Theorem ### Increasing Side ($d < n - 1$) $\mathcal{A}_d$ has $m = d + 1$ elements (columns $0$ to $d$) and $\mathcal{A}_{d+1}$ has $m + 1$ elements (columns $0$ to $d + 1$). Setting $A = \mathcal{A}_d$ and $B = \mathcal{A}_{d+1}$ indexed by column, the domination conditions match Lemma 1: $A_j < B_j$ and $A_j < B_{j+1}$. Lemma 1 gives $\operatorname{sorted}(A)_k < \operatorname{sorted}(B)_k$ for $k = 0, \ldots, m-1$. After sorting, order stat $k$ occupies column $k$ on both anti-diagonals. **Column check.** Positions $(d - c, c)$ and $(d + 1 - c, c)$ both hold order stat $c$. The lemma gives $\operatorname{sorted}(A)_c < \operatorname{sorted}(B)_c$. **Row check.** Position $(d - c, c)$ on $\mathcal{A}_d$ holds order stat $c$; position $(d - c, c + 1)$ on $\mathcal{A}_{d+1}$ holds order stat $c + 1$. From the lemma, $\operatorname{sorted}(A)_c < \operatorname{sorted}(B)_c \leq \operatorname{sorted}(B)_{c+1}$. ### Decreasing Side ($d \geq n - 1$) $\mathcal{A}_d$ has $m + 1$ elements and $\mathcal{A}_{d+1}$ has $m$ elements. Let $c_0 = c_d^-$ be the minimum column index of $\mathcal{A}_d$, so $\mathcal{A}_{d+1}$ starts at column $c_0 + 1$. Reindex: let $A_j$ be the element of $\mathcal{A}_d$ at column $c_0 + j$ (for $j = 0, \ldots, m$) and $B_j$ be the element of $\mathcal{A}_{d+1}$ at column $c_0 + 1 + j$ (for $j = 0, \ldots, m-1$). The domination at shared column $c = c_0 + 1 + j$: - **Column domination:** $\mathcal{A}_d$ at $(d - c, c)$ is one row above $\mathcal{A}_{d+1}$ at $(d + 1 - c, c)$. This gives $A_{j+1} < B_j$. - **Row domination:** $\mathcal{A}_d$ at $(d + 1 - c, c - 1)$ is one column left of $\mathcal{A}_{d+1}$ at $(d + 1 - c, c)$ in the same row. This gives $A_j < B_j$. These match Lemma 2. It gives $\operatorname{sorted}(A)_{k+1} < \operatorname{sorted}(B)_k$ for $k = 0, \ldots, m-1$. **Column check.** At shared column $c$, $\mathcal{A}_d$ holds order stat $c - c_0$ and $\mathcal{A}_{d+1}$ holds order stat $c - c_0 - 1$. Setting $k = c - c_0 - 1$: $\operatorname{sorted}(A)_{k+1} < \operatorname{sorted}(B)_k$. **Row check.** At a shared row, column $c$ on $\mathcal{A}_d$ has order stat $c - c_0$ and column $c + 1$ on $\mathcal{A}_{d+1}$ has order stat $c - c_0$. Setting $k = c - c_0$, we need $\operatorname{sorted}(A)_k < \operatorname{sorted}(B)_k$. From the lemma with distinctness: $\operatorname{sorted}(A)_k < \operatorname{sorted}(A)_{k+1} < \operatorname{sorted}(B)_k$. ### Conclusion For every adjacent pair of anti-diagonals, the row and column orderings are preserved after sorting. Since every row-adjacent and column-adjacent pair of grid positions lies on adjacent anti-diagonals, the full Young tableau property is maintained. $\blacksquare$ --- ## Remark: Why the Classical Lemma Fails The standard proof that row-sort preserves column-sortedness uses a **single domination**: $A_j < B_j$ implies $\operatorname{sorted}(A)_k \leq \operatorname{sorted}(B)_k$, but only when $|A| = |B|$. Adjacent anti-diagonals differ in length by one. With only single domination and unequal lengths, one obtains the weaker bound $\operatorname{sorted}(A)_k \leq \operatorname{sorted}(B)_{k+1}$ -- insufficient for either row or column preservation. However, the Young tableau provides **two independent domination relationships** (one from rows, one from columns). This double domination is exactly what compensates for the length mismatch. ___ ## Appendix: another sketch > Here's an alternative sketch that I find slightly more intuitive -- it builds up $\text{sorted}(B)$ inductively rather than reasoning about the whole thing at once. > > Start with $\text{sorted}(B)_0$. Double domination guarantees at least one element of $A$ is smaller than every element of $B$, so $\text{sorted}(A)_0 < \text{sorted}(B)_0$. Column 0 is sorted. > > Now build up inductively. $\text{sorted}(B)_1$ has at least two elements of $A$ smaller than it -- the witnesses come from single domination ($A_j < B_j$) at distinct indices $j$. We can't say exactly where those two witnesses land in $\text{sorted}(A)$, but two distinct elements of $A$ below $\text{sorted}(B)_1$ is enough to force $\text{sorted}(A)_1 < \text{sorted}(B)_1$. Combined with the base case $\text{sorted}(A)_0 < \text{sorted}(B)_0 < \text{sorted}(B)_1$, column 1 must be sorted, i.e. $\text{sorted}(A)_1$ exists as the 2nd element of $\text{sorted}(A)$. This also implies the row of $[\text{sorted}(A)_0, \text{sorted}(B)_1]$ is sorted. Induct -- the general step is the same argument with $k+1$ distinct witnesses. > > Unfortunately, there is one-ish wrinkle, which is probably why Claude did the counting thing. $B$ has $m+1$ elements but only indices $0$ through $m-1$ participate in single domination ($A_j < B_j$). Index $m$ has no corresponding element in $A$. So if $B_m$ lands among the $k+1$ smallest elements of $B$, we lose a witness -- single domination only provides $k$ distinct elements of $A$ below $\text{sorted}(B)_k$, one short. > > The second domination condition ($A_j < B_{j+1}$) rescues this: $A_{m-1} < B_m$, so $A_{m-1}$ is a candidate witness. If $A_{m-1}$ isn't already among our $k$ witnesses, we're done since it collapses into the normal case. If it _is_ -- meaning $B_{m-1}$ was also among the small elements of $B$ -- then $B_{m-1}$ had _two_ domination paths into $A$ (both $A_{m-1} < B_{m-1}$ and $A_{m-2} < B_{m-1}$), giving it a surplus witness. That surplus covers the deficit at $B_m$. The details of this case analysis (and the general step) are left as an exercise to the reader, but the point is that the second domination provides exactly the one extra witness that the length mismatch costs you. > > What about $\text{sorted}(B)_m$, the extra element at the end of the longer diagonal? It has no cell above it in the grid (we're on the increasing side), so there's no column constraint to satisfy.