  The left patience sorting (lPS) monoid, also known in the literature as the
Bell monoid, and the right patient sorting (rPS) monoid are introduced by
defining certain congruences on words. Such congruences are constructed using
insertion algorithms based on the concept of decreasing subsequences.
Presentations for these monoids are given.
  Each finite-rank rPS monoid is shown to have polynomial growth and to satisfy
a non-trivial identity (dependent on its rank), while the infinite rank rPS
monoid does not satisfy a non-trivial identity. The lPS monoids of finite rank
have exponential growth and thus do not satisfy non-trivial identities. The
complexity of the insertion algorithms is discussed.
  rPS monoids of finite rank are shown to be automatic and to have recursive
complete presentations. When the rank is $1$ or $2$, they are also biautomatic.
lPS monoids of finite rank are shown to have finite complete presentations and
to be biautomatic.
