I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (ones that have a binary answer). I know that any optimization problem can be turned into a decision problem by imposing a threshold on the objective function (and asking if it is greater than the threshold). So, I'm trying to find a way to convert the sorting problem into an optimization problem. Ideally, the best way to get the answer to this optimization problem should be to just sort the array.
It becomes like a mathematical problem of constructing an objective function that favors one particular permutation.
My attempts: One objective function might involve looping through the array and adding $1$ to the objective function if the successive element is larger than the current one. This does have the largest value when the array is sorted. However, one doesn't have to sort the array to get the best value of this function (simply count the entries in the array). The possibility of the array having duplicate entries can make it a little interesting, but one can still just store the distinct entries and their counts in a dictionary and get the objective function without sorting the array.
Another possibility is to loop through the array and add the difference between the next element and current one to the objective function. This seems more promising and coming up with the best objective function should require us to sort the array. But I don't have a proof for this.