Checking that the output is sorted is the easy part. Checking that the output is a (optionally stable) permutation of the input is the hard part. You can't do

Checking that the output is sorted is the easy part. Checking that the output is a (optionally stable) permutation of the input is the hard part. You can't do that dynamically if you have, for example, overwritten your input by sorting in place. And making a copy of your input is only going to be affordable in very specific and small instances on which you might as well just run a well-understood algorithm.