This question already has an answer here:
I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using comparison based algorithem) in just 6 steps. Can you guys help me out with this?