We have Desktop 10.3 installed on Win8
We have a layer with 800k records stored in FGDB
When we try to sort it in ArcMap (On OBJECTID) it takes a few minutes (4-5 minutes).
The same file is sorted in less than 10 seconds on desktop 10.0 or on different machines.
The same problem exists with all layers and all fields.
You could create a new field (say NewID with the datatype Long). Copy the values of ObjectID to NewID using field calculator.
You can create an attribute index for the NewID field.
Try sorting the table using NewID field.
Some of the original testing was done on OBJECTID that does have index.
Again, I will test it when Passover is over.
How much time it takes on your side to sort 800k records with/without index in FGDB or ArcSDE?