I was trying to find a solution. So it is not possible at all if any of the cells in the sort range are locked. Right...?Thanks Fluff
This is to inform to every one and update that I have found a solution to sort in a protected sheet without using VBA. This was shared with me.
1. Protection must initially be off for the sheet you are editing. Also be sure if there are any cells you want to let users edit (I usually have 1 or 2 columns in the table they can edit), go ahead select those cells, right click on the selection, select "Format cells...", go to the "Protection" tab, and deselect "Locked"
2. On "Review" Tab, in the "Changes" section, click on "Allow Users to Edit Ranges"
3. Click "New..."
4. In "Refers to cells:" enter either "=Table1" (don't type the quotes and replace 'Table1' with whatever the table name is, which you can see from the "Name Manager" on the "Formulas" ribbon bar; by default, if it's the only table, it will be Table1) or the entire range of cells for the table, INCLUDING THE HEADER ROW. IMPORTANT: It will not work if the header row is not included. This is one of the missing steps that I got wrong the first time I tried.
5. Click OK
6. Click "Protect Sheet..."
7. Uncheck "Select locked cells" (otherwise, users will be able to select and edit even the Protected cells -- not really protected)
8. Be sure that "Sort" and "Use AutoFilter" are both checked.
9. Optional: If any cells are supposed to be editable, be sure that "Select unlocked cells" is checked, and any other options you want to allow.
10. If you don't want users to be able to turn off protection, enter a password in the "Password to unprotect sheet:" box.
11. Click OK
There you go. Now your sheet is sortable while Protected and supports both locked and unlocked cells as you would expect Excel would work if you simply checked the Sort or AutoFilter boxes when you protected the worksheet. No VBA. Only downside to this method is that users cannot select or copy data from protected cells. If that's a requirement for you, then this is not a viable solution.