The slowness of sorting records is generally due to the sorted Field Options in Manage > Database… menu, Fields tab :
When a field is calculated AND if the calculation is not stored (always re-calculated), that defined in "Other option" tab, sorting on it can be very slow.
Of course, it is also depending of the number of records, the fact that your file is hosted, the network flow and can vary by a lot of other factors...
Anyways, you can really increase performence by setting your fields options carefully.
Sorting on a field from a related table can also slow the sort down. Also a normal data field with no index will sort much more slowly than if indexing were turned on for that field, I believe.