Bob Jolliffe <bobjolliffe(at)gmail(dot)com> writes:
> I wonder what can cause such a massive discrepancy in the sort time.
Are you using the same locale (LC_COLLATE) setting on both machines?
Some locales sort way slower than C locale does. That's not enough
to explain a 1000X discrepancy --- I concur with the other opinions
that there's something wrong with your VPS --- but it might account
for something like 10X of it.
regards, tom lane