Most Efficient Sorting Algorithm for Generated Data -

i have following formula: a=(x+x0)^.5 * (y+y0) * (z+z0)^.5

x0, y0, , z0 constant given run, may change between runs of program. x, y, , z randomly generated item , uniform integers in [0, 15]. means there 16^3=4096 possible combinations.

i trying find efficient way percentile of given value (x0, y0, , z0 given well). have 2 questions:

1. is there way create analytic formula solve percentile directly, without generating possible , sorting them?
2. if not, efficient way sort data, given have information how structured?

i kind of assumed answer #1 "no" pleasantly surprised if can come analytic solution. proceeding #2, here current progress:

data generated via 3 nested loops:

for x = 0 15    y = 0 15        z = 0 15           array(n) = a(x,y,z)           n=n+1        next z    next y next x 

we know (at least) 3 things data:

1. array(0) < array(1) < array(2)...
2. array(0) < array(16) < array(32) ...
3. array(0) < array(256) < array(512)...

so far best working algorithm mergesort starts list size 16. ignored 2) , 3) above.

note: question efficiency. have solution, slow, works, i'm looking efficient way this.

edit: here solution started come with, feels efficient, doesn't work. i'm not sure if can salvaged.

put values in 3-dimensional array (x, y, z). start (0,0,0) must minimum. next value must (1,0,0), (0,1,0), or (0,0,1). test , add. let's (1,0,0). next value must (2,0,0), (0,1,0), or (0,0,1). continue until you've added values in o(n) time.

flaw: number of possibilities isn't constrained 3. can't figure out way tell computer cells possibilities without killing efficiency gain. there may way, haven't thought of it.

edit 2: still interested in efficient sorting algorithm values generated monotonic function, since theoretically interesting question. however, since asked first if there shortcut getting percentile, have select strikingly simple "count number less a" answer.

if need know position of a in sorted list of possibilities, there no need sort possibilities (o(n log n)). it's sufficient count number of possibilities less or equal a (o(n)).

in case, function monotonic, can reduce work further: given definite values x' , z', can solve y' in a = f(x', y', z'). know there max(0, min(16, floor(y') + 1)) triples <x', y, z'> value less or equal a.

that solution quite simple. given

a=(y' + y0) * ((x'+x0) * (z'+z0))^.5 

we have

y' = / ((x'+x0) * (z'+z0))^.5 - y0 

---

python (which considered pseudocode):

def gmean(x, y):     return (x * y) ** 0.5  def count_le(a, x0, y0, z0):     count = 0     x in range(16):         z in range(16):             gm = gmean(x + x0, z + z0)             if gm == 0:                 count += 16             else:                 y = / gm - y0                 if y >= 0:                     count += min(16, 1 + int(y))     return count 

to turn result of count_le percentile, you'd have multiply 100/4096.