The answer is quite easy: Excel allows you to specify what users can and cannot do with a protected worksheet. When you display the Review tab of the ribbon and click Protect Sheet in the Protect group (Changes group in earlier versions of Excel), Excel displays the Protect Sheet dialogue box. At the bottom of the dialogue box is a long list of checkboxes. All you need to do is select what the user should be able to do with the worksheet. One of the options (you need to scroll down a bit) is Sort. If you select this option, then users can sort protected data.
There is a big caveat to keep in mind: All of the cells that will be involved in the sorting (or potentially involved in the sorting) must be unlocked. This includes any column headings for the data that may be sorted.
Before locking the worksheet, select all the cells that you want people to be able to sort. (A great way to do this is to select one of the cells then press Shift+Ctrl+8. The selected region is what Excel will sort.) With those cells still selected, display the Protection tab of the Format Cells dialogue box and clear the Locked checkbox. Now protect your worksheet and make sure you allow for sorting in the protection specifications.
If you fail to unprotect all the cells that may be involved in the sorting (even a single cell), then Excel won’t allow sorting the data on the protected worksheet, even if you’ve instructed it to allow sorting.