Must an optimization problem with a greedy algorithm belong to P? If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the problem belongs to P?
I was told it is true that problems of this type must belong to P, but I have questions about whether this is true.
It seems to me that there should be many examples of optimization problems with non-deterministic greedy algorithms.
Are there in fact counterexamples to this claim or is it necessarily true?
If the greediness here means moving on the input based on a specified score, and computation of the input item's score is polynomial, the answer is yes. It is correct.  Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the problem in polynomial time (by the greedy algorithm).
Notice that, the polynomial computability of the score is vital here. For example, if the computation of the score for each item will be an NP-complete/hard problem (for example if it is the minimum vertex covering of a graph), the statement will not be valid anymore.