This is Dash Core version v0.12.1.5 (64-bit) download?
Dogecoin has a similar issue, though in their case the wrong sort order is lexicographic and the comments suggest that locale setting may be the cause.
Sorting is handled by QT. In dash-qt...
We should start by profiling a single CPU core processing blocks of increasing size with various script types.
That will give us useful baseline measurements, and optimistic figures for multicore scaling.
I guess we're most interested in gauging what hardware is required for what tx throughput...