thank you for the log file and more details, it was useful.
We are still working on investigatation of this performance issue. Just a few ideas for now:
It's possible that it's somehow related to 2000 detail rows, because these are split into more IN (...) parts in executed SQL. If possible, could you try to select a structure which has for example <100 detail rows and test sorting on this?
Maybe you can try to switch off "Initial data retrieve" in schema editor under schema configuration. Except loading of all data in the beginning it also prevents some loading of total row count. This can be slow for 13mil rows tables. Also there is a difference between sorting using toolbar button and popup menu (we are lookin at this as well). Popup menu is freezing IJC, but toolbar button is starting sorting on background (progress bar is moving).
We will let you know soon about the progress.