The fastest sorting algorithm? (2000)(nada.kth.se)
nada.kth.se
The fastest sorting algorithm? (2000)
https://www.nada.kth.se/~snilsson/fast-sorting/
10 comments
I will quote from the linked article:
Other sorting techniques may be faster. For example, using radix sorting, you can sort n word-sized integers by scanning the data a few bits at a time. Each scan can be done in linear time, and the number of scans depends on the word length w. Hence, the time for radix sorting is proportional to nw. Here, it’s easy to make a mistake. On most computers, w is a small number (typically 32 or 64), and you might be tempted to state that radix sorting is a linear time sorting algorithm. Not so. The algorithm will only work if w ≥ log n. If not, you wouldn’t even be able to store the numbers. Since each memory address is a word consisting of w bits, the address space won’t accommodate n numbers if w < log n. Hence, in the unit-cost RAM model, radix sort also runs in time proportional to n log n.
Other sorting techniques may be faster. For example, using radix sorting, you can sort n word-sized integers by scanning the data a few bits at a time. Each scan can be done in linear time, and the number of scans depends on the word length w. Hence, the time for radix sorting is proportional to nw. Here, it’s easy to make a mistake. On most computers, w is a small number (typically 32 or 64), and you might be tempted to state that radix sorting is a linear time sorting algorithm. Not so. The algorithm will only work if w ≥ log n. If not, you wouldn’t even be able to store the numbers. Since each memory address is a word consisting of w bits, the address space won’t accommodate n numbers if w < log n. Hence, in the unit-cost RAM model, radix sort also runs in time proportional to n log n.
He's essentially cheating. When he analyzes the algorithm presented, he says "I’ll now describe an algorithm that does not depend on the word length. For any word length w, w ≥ log n, it sorts n word-sized integers in time proportional to n log log n."
But that's entirely cheating. If you give the same assumption to radix sort, then you could say "For any word length w, w ≥ log n, radix sort sorts n word-sized integers in time proportional to n". Which is much better.
The only time radix sort actually goes slower than linear time is when the size of the integers is not polynomial in n. If the size of the integers is exponential n, I think this algorithm would similarly slow down, as it would take a linear number of words to represent a single integer, meaning that it would take log n reductions to get the integers to fit into a single word, not log log n as he assumes.
But that's entirely cheating. If you give the same assumption to radix sort, then you could say "For any word length w, w ≥ log n, radix sort sorts n word-sized integers in time proportional to n". Which is much better.
The only time radix sort actually goes slower than linear time is when the size of the integers is not polynomial in n. If the size of the integers is exponential n, I think this algorithm would similarly slow down, as it would take a linear number of words to represent a single integer, meaning that it would take log n reductions to get the integers to fit into a single word, not log log n as he assumes.
I think his argument goes as follows. If you have N numbers in memory, then you have to use pointers of size log N bits. Because pointers use the same number of bits as numbers, this means that the numbers have to be log N bits. Because radix sort does one O(N) pass per bit, this means that total time will be O(NlogN).
If we sort numbers of a fixed, known, size w', that is independent of machine word size w, then the argument breaks.
If we sort numbers of a fixed, known, size w', that is independent of machine word size w, then the argument breaks.
I wish nloglogn.c would come with an open source license. I'd really like to use it.
There's faster sorting algorithms:
1) ZEN sort: O(0)
a) It is build on the realisation that it is all about numbers that do not really mean anything.
b) It converges to NOTHINGNESS.. while it deletes all data there is.
2) Intelligent design sort (also known as miracle sort) O(1)
The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.
3) Numerology Sort: O(n)
a) Employ gematria to calculate a divine hash sum of all the elements of the array, taking O(n) time. The specific method depends on the data type, and is left as an exercise to the reader.
b) Use this value to seed your PRNG.
c) Using the PRNG, sample pairs of indices and swap the indicated elements. Do this 4n times.
d) If the array is not sorted at this point, you have likely made an error in computing your hash. A debugging message is numerologically embedded in the output array that will guide you.
(Gematria: https://en.wikipedia.org/wiki/Gematria )
4) Sleep sort: O(largest number to be sorted)
a) read a number to be sorted, call it n
b) start a new thread, that sleep n seconds
c) insert the number in the result array
5) Chuck Norris sort
Chuck Norris once wrote by far the fastest sort algorithm ever. In Python:
1) ZEN sort: O(0)
a) It is build on the realisation that it is all about numbers that do not really mean anything.
b) It converges to NOTHINGNESS.. while it deletes all data there is.
2) Intelligent design sort (also known as miracle sort) O(1)
The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.
3) Numerology Sort: O(n)
a) Employ gematria to calculate a divine hash sum of all the elements of the array, taking O(n) time. The specific method depends on the data type, and is left as an exercise to the reader.
b) Use this value to seed your PRNG.
c) Using the PRNG, sample pairs of indices and swap the indicated elements. Do this 4n times.
d) If the array is not sorted at this point, you have likely made an error in computing your hash. A debugging message is numerologically embedded in the output array that will guide you.
(Gematria: https://en.wikipedia.org/wiki/Gematria )
4) Sleep sort: O(largest number to be sorted)
a) read a number to be sorted, call it n
b) start a new thread, that sleep n seconds
c) insert the number in the result array
5) Chuck Norris sort
Chuck Norris once wrote by far the fastest sort algorithm ever. In Python:
def sort(x):
# I will roundhouse kick any array that isn't sorted at this point. Twice.
return xQuantum sort: O(n)
1. Use quantum device to randomize order of array
2. Check if sorted
3. If not sorted, destroy universe
In all universes which are left, the array is sorted. (Dependencies: Many worlds interpretation, Doomsday device.)
Edit: Formatting.
1. Use quantum device to randomize order of array
2. Check if sorted
3. If not sorted, destroy universe
In all universes which are left, the array is sorted. (Dependencies: Many worlds interpretation, Doomsday device.)
Edit: Formatting.
What happens if you have a bug in there ?
I'm surprised you didn't list Bogo Sort (Monkey Sort) where the array order is randomised (shuffled) until it is properly sorted: https://en.wikipedia.org/wiki/Bogosort
The Wikipedia link also lists the Goro-, Bogobogo, and Bozosort variants.
The Wikipedia link also lists the Goro-, Bogobogo, and Bozosort variants.
> 5) Chuck Norris sort
i thought it was more like:
i thought it was more like:
def sort(x):
if x == gay || x == intelligent:
return hate()
elif x == president:
return question_birth()
return 1
> The algorithm will only work if w ≥ log n.
What does that mean ? It doesn't make sense to me. The algorithm will work regardless of the magnitude of w relative to log(n).
Radix sort will be faster than n log(n) if w < log(n). I would add that it is only worth to use if w << log(n). In fact radix sort process the sorting by groups of bits, so w is usually smaller than the number of bits.