complicated combinatorial algorithms with good descriptions For educational purposes, I am looking for an example of a complicated, elementary, but very well-explained combinatorial algorithm.
Such an example might be a bijection between two easily described sets, where the bijection involves many case distinctions.
Of course, "very well-explained" is completely subjective, but that is really the focus of the question.
 A: I have a candidate. Let $\mathcal{A_n} = \{w \in S_n: w_1 = w_n+1, \mbox{Fl}(w_2 \dots w_{n-1}) \in \mathcal{A}_{n-2} \}$ where $\mbox{Fl}$ is the flatten operator mapping a word with distinct entries to the permutation with the same relative order.
In one of my papers, we show that
$$
\sum_{w \in \mathcal{A}_{2n+1}} F_w  = s_{\delta_n}^2
$$
where $F_w$ is the Stanley symmetric function and $\delta_n = (n{-}1,n{-}2,\ldots,1)$ (a similar result holds for $\mathcal{A}_n$ with $n$ even).
We have since given two bijective proofs of this identity - one based on an insertion algorithm and the other based on a variant of the Little bijection.
What we don't mention is that I have a more or less complete document defining a bijection
$$
\mbox{SYT}(\delta_{2n}\setminus (n)^n) \to \mathcal{R}(n{+}1\ n \dots1 \ 2n{+}2\ 2n{+}1 \dots n{+}1)  \to \bigcup_{w \in \mathcal{A}_{2n+1}} \mathcal{R}(w)
$$
where $\mathcal{R}(w)$ is the set of reduced words of $w$.
The first arrow here follows immediately from the literature, but the second requires repeated application of a very precise choice of Little bumps.
My implementation of the algorithm in SAGE has a little over 100 lines of code (not counting an implementation of the quite technical Little bijection), mostly to describe which Little bumps to perform.
The description of the algorithm in the uncompleted paper takes about 2/3 of a page once all terminology has been established.
The three main steps call each other recursively and repeatedly, with various cases determining which step to return to.
Converting the description to pseudo-code would make it much longer.
One attractive feature of this map for your purposes is that it runs into quite subtle issues.
Initial attempts to code the bijection would usually succeed for instances of the problem with $n \sim 50$, while for $n \sim 100$ they tended to get caught in infinite loops.
With a few more major pieces of casework, the algorithm could be proved to terminate.
In the end, it was relatively easy to see the map is an injection, but I was missing a key technical lemma about Little bumps to show it was invertible.
Since better proofs are available, I will probably never write the full details, but I am happy to share a correct implementation or a complete description of the map.
A: I believe proposition 11 in this paper might fulfill your requirements - it describes a bijection between sets (certain fillings of tableaux).
The properties of the bijection actually defines it uniquely, so the steps to perform the algorithm is quite easy.
The kicker - to prove that it is indeed a bijection, that it works, requires induction between several sub and sub-sub cases. A second part of this check requires to check that it works on all $3\times 2$-diagrams, and relative orderings of the entries. This is a few cases to go through, where "a few" is about $280.000$ (we uses two independent computer programs to do these steps).
EDIT: Well, seeing your comment - you might also be interested in proofs that use some type of sign-reversing involution. This might sometimes involves some quite non-trivial case by case analysis, and you essentially describe an algorithm on how to do this. 
My suggestion is to ask someone implement the bijection in a different language - sometimes an experienced math coder can gather several subcases into fewer ones by choosing some sneaky conventions (smart choice of indexing, etc.)
