Given a countable set X (usually taken to be the natural numbers or
integers), an infinite permutation, \pi, of X is a linear ordering of X. This
paper investigates the combinatorial complexity of infinite permutations on the
natural numbers associated with the image of uniformly recurrent aperiodic
binary words under the letter doubling map. An upper bound for the complexity
is found for general words, and a formula for the complexity is established for
the Sturmian words and the Thue-Morse word.