What is wrong with the following $P$ problem? Our teacher gave us the following statement and we were wondering what is wrong with it.


  Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$,
  we cannot check for each permutation whether it is sorted, in a total time which is polynomial in $n$.
  Therefore, sorting $A$ cannot be in $P$.


Obviously this is wrong.
My friend thought it should just be: therefore sorting $A$ cannot be in $NP$.
Is this correct or are we thinking about it to easily?
Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )