In your sorting macro, provide the password to unprotect the sheet first, before the sorting is actually done. Then password protect the sheet at the end.

If the sort will always be alphabetical, include a command button tied to the sort macro. That way the sort will occur in a blink of an eye and the user won't be able to perform any functions on the workbook ... just the sort.