Make a list of all States (say in ColumnE, assuming your data is in ColumnA:B starting in Row2) and in:
C2 enter: =VLOOKUP(A2,E:E,1,0)
D2 enter: =VLOOKUP(B2,E:E,1,0)
copy both down to suit.
Sort A:C on ColumnC and for #N/A values in ColumnC switch over columns A and B. Reinstate the formulae for those rows, then sort A:D on ColumnD and for values other than #N/A switch over Columns A and B.
Redo formulae as a check.