Sorting Excel 2 or more Columns

Oftentimes, I create or update 5 to 6 columns with code number for each city as my sorting key, arranged in ascending order from 022 to 600. There are about 300 cities in my spreadsheet. The cities are entered down to 66 lines and continue to the next right column (like a newsletter style) and so on.

However, as new cities come in with new code number, I find it difficult to insert that new city in the middle of column without moving up or down the rest of the cities (thus preserving the 66lines for printing report). Then I entered the new cities starting at the last name and sorted along with the existing cities but the result was not what I wanted. The header became part of the sorting and was placed at the bottom or middle of the columns. Trying it again with Excel's suggestions from Help, I always came up with different results. The new cities are not sorted but remained where they were.

How do I sort this? With any word processor, I can sort names, numbers with ease but with Excel, I am missing a step or so. Please help me. If you need copy of it, please let me know.