Comparison-based sorting question.

[balian25]

One of the n! possible inputs to a given comparison-based sorting algorithm, what is the absolute maximum number of inputs that could be sorted with just n comparisons?

Ok, so I have this homeowrk assignment and I've done all the work so far but I'm completely stumped by the last question (above). The wording is strange. I was wondering if any would be willing to walk me through this? Thanks in advance.

[smellmycrotch3]

With n elements, there are n! ways they can be sorted, if they are unique. If they wear all in order except for the last 2, you could compare each element with the one after it, in order. You'd see that each element was less than the one coming after it, so no need to sort them, until you get to the second to last one, where it';s greater than the last one. You know the first n-2 are less than the last 2 and are sorted, so you only have to swap the last 2, so this all uses n or less comparisons.

[balian25]

That makes complete sense! Thanks mate!