Seeding controls the random number stream you generate. If you seed with the same seed, you'll get the same sequence every time. You're seeding here with the same number each time (because it won't take even 1ms to do the sort), so the nextInt() will always return the same value. Thus it will always return the same sort. Since your data is sorted coming in, that causes it to stay in the same order.
If you want to seed correctly, create the Random object once, and call it rather than recreating with the same seed each time.