I had lots of fun with last month's riddle, and decided to make this month's
riddle a follow-up to it. For this reason, this month's riddle starts with
a warning:
The solution to last month's riddle had, at its core, the ability to pack
the data from many integers into a single integer. For example, if we have
an array of _{-1}
non-negative
integers, we can encode all of it into a single integer as the sum of
X*2_{i}^{i*width}, once an appropriate
value of width is chosen. For a person knowing n and width
the information in the sum is equivalent to the information in the entire
array.
Last month's riddle asked for a sorting procedure that sorts
On the face of it, the obvious answer is "yes": one needs O( Consider, therefore, the following procedure, given here in Python code: def sorting(array): size=len(array) if size==0: return [] minimum=min(array) nonnegative_array=[x-minimum for x in array] maximum=max(nonnegative_array) width=int(log(max(maximum,1))/log(2))+1 encoded_array=encode(nonnegative_array,width) encoded_sorted_array=fast_sorting(encoded_array,size,width) sorted_array=decode(encoded_sorted_array,size,width) return [x+minimum for x in sorted_array] def encode(array,width): encoded_array=0 for i in range(len(array)): encoded_array+=array[i]<<(width*i) return encoded_array def decode(array,size,width): decoded_array=[0]*size for i in range(size): decoded_array[i]=array & ((1<<width)-1) array>>=width return decoded_arrayThis implementation of "sorting" encodes an array as an integer, sends it to "fast_sorting", then gets a result and decodes it into an output array. Given an appropriate implementation of "fast_sorting", what the function "sorting" does is to sort the input array. Effectively, "fast_sorting" is the sorting routine, and all else is just code to handle reformatting of its input and output. Regardless of how much time it takes "sorting" to run, there is no reason to assume "fast_sorting" can't have a lower complexity than O( n).
This month's riddle: design an algorithm for "fast_sorting" |
## List of solvers:Marcos Simões (8 January 21:54) |

Elegant solutions can be submitted to the puzzlemaster at __riddlesbrand.scso.com__.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!