3 ms·
My contribution: Power Sort. Start with p=0 and add 2^n for each n. Then subtract the largest power of 2 successively to get your integers ordered. Con: p wil
by forinti 5y ago
My contribution: Power Sort.
Start with p=0 and add 2^n for each n. Then subtract the largest power of 2 successively to get your integers ordered.
Con: p will be very big.
Pro: you don't need ifs!
- Snild 5y agoOoh, that's a fun one. Another con: you'd better hope your input contains no duplicates. :)
- forinti 5y agoEasily solvable with a hash. I have thought this through (I'm ashamed to admit).
- dbaupp 5y agoDuplicates could also be handled by using (L+1)^n, rather than 2^n, where L is the length of the input: even if all elements are identical one will end up with a unique value p = L * (L+1)^n. For an efficient implementation, one might want to round L+1 up to the nearest power of 2 to get crucial micro-optimisations based on instructions for bit scanning. (I think this ends up being a very complicated phrasing of a counting sort.)
- Paedor 5y agoFun fact, when you consider the bits required to contain p, this is equivalent to bucket sort with a bucket size of 1.