You have 2 choices:
1) Unprotect the sheet then change the Security for those 4 columns (via
Format --> Cells --> [Protection] and clearing the "Locked" box for them.
Then put your sheet back into protection mode with the option to permit
sorting still selected.
2) Use a VBA solution that would unprotect the sheet, perform the sort, put
the sheet back into protected mode.