Let me see if I get this right... you have a 4000+ array and you want to sort it... in PAWN... in a thread with a time-limited execution... under HL ?!?
I'm not the biggest fan of SQL but in your case it's the ONLY solution.
EDIT: @Sylwester: Regrdless of the algorithm, the overhead is too much.
Even if the SortCustom2D works with ~3000 entries, it does not mean it's the right way to do this.