  In the present work, we study the hierarchy of $p$-sortable languages:
regular languages accepted by automata of width $p$. In this hierarchy, regular
languages are sorted according to the new fundamental measure of NFA complexity
$p$. Our main contributions are the following: (i) we show that the hierarchy
is strict and does not collapse, (ii) we provide (exponential) upper and lower
bounds relating the minimum widths of equivalent NFAs and DFAs, and (iii) we
characterize DFAs of minimum $p$ for a given $\mathcal L$ via a
co-lexicographic variant of the Myhill-Nerode theorem. Our findings imply that
in polynomial time we can build an index breaking the worst-case conditional
lower bound of $\Omega(\pi m)$, whenever the input NFA's width is at most
$\epsilon \log_2 m$, for any constant $0 \leq \epsilon < 1/2$.
