  Various forms of sorting problems have been studied over the years. Recently,
two kinds of sorting puzzle apps are popularized. In these puzzles, we are
given a set of bins filled with colored units, balls or water, and some empty
bins. These puzzles allow us to move colored units from a bin to another when
the colors involved match in some way or the target bin is empty. The goal of
these puzzles is to sort all the color units in order. We investigate
computational complexities of these puzzles. We first show that these two
puzzles are essentially the same from the viewpoint of solvability. That is, an
instance is sortable by ball-moves if and only if it is sortable by
water-moves. We also show that every yes-instance has a solution of polynomial
length, which implies that these puzzles belong to in NP. We then show that
these puzzles are NP-complete. For some special cases, we give polynomial-time
algorithms. We finally consider the number of empty bins sufficient for making
all instances solvable and give non-trivial upper and lower bounds in terms of
the number of filled bins and the capacity of bins.
