Using your Head is Permitted

Spoiler alert: The following description contains hints regarding the solution of last month's riddle. If you still mean to tackle that other riddle, you may want to hold on before you continue to this one.

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 X₀, ..., X_n-1 non-negative integers, we can encode all of it into a single integer as the sum of X_i*2^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 n integers in O(n) under a specified computational model. This month's riddle continues to use the same model (described there in full), and asks the question of whether O(n) really is the best one can hope for.

On the face of it, the obvious answer is "yes": one needs O(n) time merely to read the input array and to output the result array. However, this problem can be circumvented: if the information from an entire array can be packed into a single integer, this integer can be read/written in O(1).

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_array

This month's riddle: design an algorithm for "fast_sorting" n integers that takes O(1) time.

List of solvers: