Most Efficient Sorting Algorithm for Generated Data
<p>I have the following formula: A=(x+x0)^.5 * (y+y0) * (z+z0)^.5</p>

<p>x0, y0, and z0 are constant for a given run, but may change between runs of the program.  x, y, and z are randomly generated for an item and are uniform integers in [0, 15].  This means there are 16^3=4096 possible combinations.  </p>

<p>I am trying to find the most efficient way to get the percentile of a given A value (x0, y0, and z0 will be given as well).  I have two questions:</p>

<ol>
<li>Is there a way to create an analytic formula that will solve for percentile directly, without generating all possible As and sorting them?</li>
<li>If not, what is the most efficient way to sort this data, given that I have some information about how it will be structured?</li>
</ol>

<p>I kind of assumed the answer to #1 is "no" but will be pleasantly surprised if someone can come up with an analytic solution.  Proceeding with #2, here is my current progress:</p>

<p>Data will be generated via 3 nested loops:</p>

<pre><code>For x = 0 to 15
   For y = 0 to 15
       For z = 0 to 15
          array(n) = A(x,y,z)
          n=n+1
       Next z
   Next y
Next x
</code></pre>

<p>We know (at least) 3 things about this data:</p>

<ol>
<li>array(0) &lt; array(1) &lt; array(2)...</li>
<li>array(0) &lt; array(16) &lt; array(32) ...</li>
<li>array(0) &lt; array(256) &lt; array(512)...</li>
</ol>

<p>So far my best working algorithm is a mergesort that starts with list size 16.  However this ignored 2) and 3) above.  </p>

<p>Note: My question is about efficiency.  I have a solution, that is slow, but works, so what I'm looking for is the most efficient way to do this. </p>

<p>EDIT: Here is a solution I started to come up with, which feels like it would be the most efficient, but it doesn't work.  I'm not sure if it can be salvaged.  </p>

<p>Put your values in a 3-dimensional array (x, y, z).  Start with (0,0,0) which must be the minimum.  The next value must be (1,0,0), (0,1,0), or (0,0,1).  Test and add.  Let's say it was (1,0,0).  Then the next value must be (2,0,0), (0,1,0), or (0,0,1).  Continue until you've added all the values in O(n) time.  </p>

<p>FLAW: The number of possibilities isn't always constrained to 3.  I can't figure out a way to tell the computer which cells are possibilities without killing the efficiency gain.  There may be a way, but I just haven't thought of it.</p>

<p>Edit 2: I am still interested in the most efficient sorting algorithm for values generated from a monotonic function, since it is theoretically an interesting question.  However, since I asked first if there was a shortcut to getting percentile, I have select the strikingly simple "count the number less than A" as the answer.</p>