News for hackers. Stuff that matters.

A comment on Writing a Faster Sorting Algorithm. Parent comment

Re:Writing a Faster Sorting Algorithm by raverbashing on Tuesday January 03, 2017 @09:23AM (#13309283)
I think there's a (provable) mathematical impossibility to have a general O(N) sorting algorithm

Basically, how many elements do you have to move in a list of N elements to end up with one of the possible orderings

[ Parent | on HN ]
Re:Writing a Faster Sorting Algorithm by Xorlev on Tuesday January 03, 2017 @09:34AM (#13309344)
It's not impossible to have a O(N) sorting algorithm if you add more constraints, e.g. use operations other than comparisons.

Most people would be fine with a hybrid radix sort for day to day use.

[ Parent | on HN ]
Re:Writing a Faster Sorting Algorithm by maweki on Tuesday January 03, 2017 @09:34AM (#13309342)
You only ever have to move every element once to get a (pre-known) permutation that represents the sorted list.

The problem is the information in a permutation (n! possible orderings) and one can only ever "throw away" half of them on every comparison, leading to log_2(n!) or nlog(n).

[ Parent | on HN ]