It's might not be fast, but you could tie the array and proxy all methods straight through to the normal behaviour apart from STORE, which would just set a flag which you could test.

There'll be some overhead, but it might be less than a custom sort routine, I'm not sure.

See Tie::Array for documentation on how to go about this, I think you just need to inherit from Tie::StdArray and overload STORE.