Understanding Martin Farach's suffix tree algorithm
Not a complete answer but I hope this helps. 

re :


  Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.


Let, 

$l$ - list 

$g$ - ranks of elements of $l$ in $sorted(l)$

You can easily recover $sorted(l)$ using $l$ and $g$. You just put $i^{th}$ element of $l$ at position $g[i]$ in some new array $A$, like this, 

for i = 0 to len(l): 
   A[g[i]] = l[i]


Fill out following $A$ to see it. 

l = [3, 2, 4] 

g = [2, 1, 3] 

A = [ , , ]