  We introduce a permutation analogue of the celebrated Szemeredi Regularity
Lemma, and derive a number of consequences. This tool allows us to provide a
structural description of permutations which avoid a specified pattern, a
result that permutations which scatter small intervals contain all possible
patterns of a given size, a proof that every permutation avoiding a specified
pattern has a nearly monotone linear-sized subset, and a ``thin deletion''
result. We also show how one can count sub-patterns of a permutation with an
integral, and relate our results to permutation quasirandomness in a manner
analogous to the graph-theoretic setting.
