Postgres: Performance Issue: Query on enormous data fails to use index
Your costs are on your WHERE predicate for ts.status.
You can see in the explain it's doing a Seq Scan for 400,951 rows with a cost of 10,628,176.10.
While having an index that is based on the ORDER BY fields in a query can help performance with the sorting, generally you should focus more on indexing based on your predicates (JOIN, WHERE, and HAVING clauses) because it won't have to do a Sequential Scan rather it can use the index to scan or seek even.
In this case if you had an index on the status column instead, your performance would likely be better (regardless sorting on your ORDER BY clause).
The difference in performance you're currently seeing is probably a difference in query plan between when you use and remove the ORDER BY clause that happens to be more efficient altogether. If you ran an explain for the query without the ORDER BY clause, I'm sure you'd see different operations occuring. But again, proper indexing on the status field should give you consistency in performance, either way.