Resorting Auto Numbering

*I know that this may not be the best way of resolving the problem but this is not the actual problem but my way to simplify of explaining the "problem".

I have a Table with 3 fields.
Field 1 - Auto Number
Field 2 - First Name
Field 3 - Last Name

Initially, the Table was sorted via First Name,
but now, there is a change in requirement to sort by Last Name.

Next requirement is to number (Auto Number) according to the Last Name.

Current Sorted via First Name
Auto Number - First Name - Last Name
1 - Ben - Young
2 - Chuck - Norris
3 - Dennis - Johnson
4 - Ernest - Anderson

If sorted via Last Name
4 - Ernest - Anderson
3 - Dennis - Johnson
2 - Chuck - Norris
1 - Ben - Young

Desired result
to Sorted via Last Name & (Auto Number) via sort.
Auto Number - First Name - Last Name
1 - Ernest - Anderson
2 - Dennis - Johnson
3 - Chuck - Norris
4 - Ben - Young

Is there a way to do renumber / resort the auto number this?



*I have thousands of records....