The linear parallel-runtime conjecture for the step-wise odd-even algorithm

Consider the step-wise odd-even algorithm depicted in Figure, and let $N$ denote the number of elements being sorted. Its sequential worst-case runtime is compared with Bubble Sort, while parallelization executes the applicable row and column operations simultaneously. Linear parallel-runtime conjecture. The step-wise odd-even algorithm depicted in Figure runs like Bubble Sort in worst-case time $\mathcal{O}(N^2)$, and after parallelization in $\mathcal{O}(N)$. The source states that only experimental results are available beyond the general upper bound of $\mathcal{O}(N!)$ and presents this conjecture as motivated by first experiments and intuition; its status is unresolved.