It is not hard to handle addresses that are in the specific form you gave in your example. But what about addresses like:
345 E. 23rd Ave. (sort this on '23rd'?)
345 23rd Ave. S.
612 NE Apple Way (I assume you would want to sort this on Apple, not NE)
PO Box 2115 (should PO Box 2115 sort before or after P.O. Box 2114?)
13227 County Highway 7
One Central Plaza
Do you have to be able to handle such a wide range of variations? There are dozens of variations of prefixes and suffixes.