My read of the original question is that he's not asking "how do I tell if the array has been sorted yet?" but rather "I just sorted an array; how can I tell whether the order was changed?" Inserting a non-sorted element doesn't really apply to the question that I think was asked, other than by providing the trivial answer of "you now know that it was changed because you deliberately made it unsorted first".

As for an actual answer, that'd take some benchmarking of different detection methods to be sure what's fastest, but my money's on the MD5 solution, especially for large arrays.