title: sorted insert into a fixed sized array with duplication
body: <p>I am trying to find the most efficient C program to store N largest values from a stream of incoming data. Eg. Assume that the incoming data is 32bytes each and is a continuous stream from a sensor, I need to store the N largest values (duplicates allowed) from the stream.
  The simple approach would be to iterate and find the position and then move all the elements below by one (potentially discarding the current smallest value).  Is there a better way of doing this?</p>
  <p><a href="https://id.atlassian.com/login?application=bitbucket&amp;continue=https://bitbucket.org/account/signin/?redirectCount=1&amp;next=%252Fderosier%252F12bit_sort%252Fsrc%252F7d3319882f66%253Fat%253Dmaster" rel="nofollow noreferrer">Source</a></p>
  <pre><code>//MAX_KEEP    32
  
  
  typedef struct accel_sys
  {
      FILE *infile;
  
      /* Data for largest and last */
      u32 largest[MAX_KEEP]; /* largest in highest index, smallest in lowest index */
      u32 last[MAX_KEEP]; /* circular buffer */
      u8 last_start; /* points to the oldest value */
  
      /* Data for reading and processing the file */
      u8 last_byte;
      Bool even;
      int num_read;
  
  } accel_t;
  
  typedef accel_t * accel_h;
  static void store_max(accel_h accel, u32 cur_value)
  {
      int i = MAX_KEEP-1;
      int j = 0;
  
      while(i &gt;= 0)
      {
          if( cur_value &gt; accel-&gt;largest[i] )
          {
              /* found it */
              
              break;
          }
          i--;
      }
  
      /* i &lt; 0 if the value doesn't belong in the array, do nothing in that case */
      if( i &gt;= 0 )
      {
          /* Move everything lower than cur_value down, losing the last value,
           * then store our new value in our found spot */
          j = 0;
          while( j &lt; i )
          {
              accel-&gt;largest[j] = accel-&gt;largest[j+1];
              j++;
          }
          accel-&gt;largest[i] = cur_value;
      }
  
      
  }
  </code></pre>