title: What is the complexity of this specialized sort
body: <p>I would like to know the complexity (as in O(...) ) of the following sorting algorithm:</p>
  
  <ul>
  <li>There are B barrels</li>
  <li>that contain a total of N elements, spread unevenly across the barrels.</li>
  <li>The elements in each barrel are already sorted.</li>
  </ul>
  
  <p>The sort combines all the elements from each barrel in a single sorted list:</p>
  
  <ul>
  <li>using an array of size B to store the last sorted element of each barrel (starting at 0)</li>
  <li>check each barrel (at the last stored index) and find the smallest element</li>
  <li>copy the element in the final sorted array, increment the array counter</li>
  <li>increment the last sorted element for the barrel we picked from</li>
  <li>perform those steps N times</li>
  </ul>
  
  <p>or in pseudo code:</p>
  
  <pre><code>for i from 0 to N
      smallest = MAX_ELEMENT
      foreach b in B
          if bIndex[b] &lt; b.length &amp;&amp; b[bIndex[b]] &lt; smallest
              smallest_barrel = b
              smallest = b[bIndex[b]]
      result[i] = smallest
      bIndex[smallest_barrel] += 1
  </code></pre>
  
  <p>I thought that the complexity would be O(n), but the problem I have with finding the complexity is that if B grows, it has a larger impact than if N grows because it adds another round in the B loop. But maybe that has no effect on the complexity?</p>