[tim-peters]

Sorry, nope. There aren't n permutations you're searching through, but the factorial of n to search through. That's the heart of the information-theoretic proof that no comparison-based sorting algorithm can do better, on average, than needing a number of comparisons equal to the base-2 logarithm of the factorial of n. Which, as already said, is O(n log n).

[pg_bot]

No, I understand that there are n! permutations. Again you aren't actually searching through the permutations. You're running comparisons on the data to reduce the set of possible permutations to the one it has to be. (pigeon hole principle) I believe my point still stands. You should be able to cut the search space in half with one comparison every single time, which should perform the same as a binary search.

Edit: You are correct I made a mistake in my big O notation, it should be O(n log n).