Finite state transducer that sorts Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers are best.)
If you allow me to give an answer that uses "technical" terminology: the output of a finite state transducer on any given regular language is again a regular language. The sort of regular $(ab)^*$ equals non-regular $\{ a^nb^n \mid n\ge 0\}$. Thus that cannot be performed by a FST.

(added) The fact that regular languages are closed under FST is a consequence of Nivat's Theorem. Every FST $T$ can be decomposed into a regular language $R$, and morphisms $g,h$ such that $T(L) = g(h^{-1}(L) \cap R)$. In short $R$ consists of "letters" of the form $(a,b)$ where $a,b$ are from the input and output alphabets respectively (or empty), and $h,g$ select  the input/ output components from those pairs.