A radix sort which assumes that name is the least significant digit, and state the most significant would be the best approach. Let me illustrate with an example. Assume that we have the following records:
| Record | Name | County | State |
R1 |
Andrews |
Brown McLean Green Brown McLean Brown Peach Orange |
WI IL IN WI IL WI WI IN |
The name and the county are stored as arrays with blanks appended to the end. The state is stored as a two character array. We assume that strcmp() is used to compare the strings.
The first pass sorts the names into twenty-six buckets based on the first character of the last name. It would produce the following results.
Durer Apple Baker Durer Edwards Freed Kane Wood Andrews ---------------------------------------------------------------- A B .... D E F ... K ... W
After this pass the records are ordered as follows:
Andrews → Apple→ Baker→Durer→ Edwards→ Freed→ Kane→ Wood
The second pass sorts by county. It also uses twenty-six buckets indexed by the first character of the county name. This pass produces the following bucket structure. The county names are included for reference.
Durer Apple Freed Andrews Edwards Baker Kane Wood ---------------------------------------------------------------- (Brown) (Green) (McLean) (Orange) (Peach)
The records would be in the following order after this pass. (They are referenced by last name only):
Andrews → Apple → Durer → Edwards → Baker→ Freed → Wood → Kane
The last pass sorts by states and uses twenty buckets indexed by the first character in the state's name. Since the
previous passes sorted by name and county, this order will bemaintained in the last pass.
Wood Kane Edwards Durer Freed Apple Baker Andrews --------------------- The records would be in the following order after this pass. Baker McLean IL Freed McLean IL Edwards Green IN Wood Orange IN Andrews Brown WI Apple Brown WI Durer Brown WI Kane Peach WI
As the list shows, the records are arranged alphabetically by state. Within each state they are arranged alphabetically by county, and within each county they are arranged alphabetically by name.