2 ms·

I was thinking about how to make sorting faster the other day and was toying around with the idea of a permutation sort. If you think about a list of items gene

by pg_bot 5y ago

I was thinking about how to make sorting faster the other day and was toying around with the idea of a permutation sort. If you think about a list of items generally (at least) one of the permutations of the list is guaranteed to be the correct sort order. Theoretically you should be able to do a binary search to find a correct permutation since there should always be a comparison you can do to reduce the search space by half. You should be able to go faster if there is duplicated data since there are multiple permutations of the list that would work.

saagarjha 5y ago
Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.
- pg_bot 5y ago
  You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)
  - saagarjha 5y ago
    No, I understand your algorithm, I’m just saying that you’ll start with n! permutations and halve that with each step. This will require log(n!) steps.
  - tim-peters 5y ago
    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 5y ago
      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).
lifthrasiir 5y ago
That wouldn't work for general n, but for smaller n, optimized sorting libraries frequently use size-optimal sorting networks [1] which effectively do the same thing (partitioning permutations into two halves with the minimal size difference). [1] https://en.wikipedia.org/wiki/Sorting_network#Optimal_sorting_networks https://en.wikipedia.org/wiki/Sorting_network#Optimal_sortin...

by pg_bot 5y ago

saagarjha 5y ago

Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.

pg_bot 5y ago
You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)
- saagarjha 5y ago
  No, I understand your algorithm, I’m just saying that you’ll start with n! permutations and halve that with each step. This will require log(n!) steps.
- tim-peters 5y ago
  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 5y ago
    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).

lifthrasiir 5y ago

That wouldn't work for general n, but for smaller n, optimized sorting libraries frequently use size-optimal sorting networks [1] which effectively do the same thing (partitioning permutations into two halves with the minimal size difference). [1] https://en.wikipedia.org/wiki/Sorting_network#Optimal_sorting_networks https://en.wikipedia.org/wiki/Sorting_network#Optimal_sortin...