Hi 'bert,
Pretty standard rules: Numbers are sorted by their numeric values, strings are sorted using alphabetical sorting. The value in a cell can be a number or it can be a string, but it can't be both.
Here's a couple of examples of a formula that may speed your task of inserting leading zeros to the number portions of your strings. As written, the method will require an added column for each category. The process is cumulative, so you should end up with all of the letter and number combinations listed in the final column.
Select that column, Copy, then with the column still selected, go Edit (menu) Paste Values. (This may be called 'Paste formula results' in the current version of Numbers.)
Once that's done, you can delete the intervening calculation columns (and the original column containing the unconverted 'numbers').
In the example, the original 'numbers' are in column D, Column E contains the formula that converts the 'a' values (and copies of the original values in the sf category), and column F contains copies of the converted 'a' values and the newly converted 'sf' values.
E2: =IF(LEFT(D,1)="a",LEFT(D,1)&RIGHT("0000"&RIGHT(D,LEN(D)-1),4),D)
F2" =IF(LEFT(E,2)="sf",LEFT(E,2)&RIGHT("0000"&RIGHT(E,LEN(E)-2),4),E)
The bold parts of the second formula show the edits needed for each successive column (new letter category code inside the quotes, and the length in characters of the new letter category code in the three locations shown. The formula may be entered in cell E2, then filled right for as many columns as there are categories. After editing as described, the formulas may be filled down to the last row containing entries.
Here is an improved version of the same formula. This version gets the letter category code from the top cell in each of the columns, and calculates the length of that code in the three places shown in bold above, IOW, it does the editing above automatically,using the category codes you enter in row 1 of each column, as you fill it across and down.
E2: =IF(LEFT(D,LEN(E$1))=E$1,LEFT(D,LEN(E$1))&RIGHT("0000"&RIGHT(D,LEN(D)-LEN(E$1)) ,4),D)
Enter the codes ( a, sf, etc) in row 1 of each new column column to be used in the conversion.
Enter the formula in E2 (row 2 of the new column to the right of the column containing your original numbering).
Fill the formula right to the last new column to be used in the conversion.
Fill all formulas down tote end of the table.
Images:
Unsorted table (first 18 rows). Note that 'a' values have been converted in column E, while 'sf' values have not.

Sorted on values in column F. The gap between a0012 and a0029 is where I had inserted a set of sf values.

Further down the sorted table, showing the cross from a0099 to a0100, and the first five rows of sf items:

Note: Column B contains a set of generated random numbers used to 'unsort' the table after generating the 'original numbers' in column D.
Regards,
Barry