In 1966, Claude Berge proposed the following sorting problem. Given a string
of $n$ alternating white and black pegs on a one-dimensional board consisting
of an unlimited number of empty holes, rearrange the pegs into a string
consisting of $\lceil\frac{n}{2}\rceil$ white pegs followed immediately by
$\lfloor\frac{n}{2}\rfloor$ black pegs (or vice versa) using only moves which
take 2 adjacent pegs to 2 vacant adjacent holes. Avis and Deza proved that the
alternating string can be sorted in $\lceil\frac{n}{2}\rceil$ such {\em Berge
2-moves} for $n\geq 5$. Extending Berge's original problem, we consider the
same sorting problem using {\em Berge $k$-moves}, i.e., moves which take $k$
adjacent pegs to $k$ vacant adjacent holes. We prove that the alternating
string can be sorted in $\lceil\frac{n}{2}\rceil$ Berge 3-moves for
$n\not\equiv 0\pmod{4}$ and in $\lceil\frac{n}{2}\rceil+1$ Berge 3-moves for
$n\equiv 0\pmod{4}$, for $n\geq 5$. In general, we conjecture that, for any $k$
and large enough $n$, the alternating string can be sorted in
$\lceil\frac{n}{2}\rceil$ Berge $k$-moves. This estimate is tight as
$\lceil\frac{n}{2}\rceil$ is a lower bound for the minimum number of required
Berge $k$-moves for $k\geq 2$ and $n\geq 5$.
