I would like to know the complexity (as in O(...) ) of the following sorting algorithm:

• there are B barrels
• that contains a total of N elements, spread unevenly across the barrels.
• the elements in each barrel are already sorted

The sort takes combines all the elements from each barrel in a single sorted list:

• using an array of size B to store the last sorted element of each barrel (starting at 0)
• check each barrel (at the last stored index) and find the smallest element
• copy the element in the final sorted array, increment array counter
• increment the last sorted element for the barrel we picked from
• perform those steps N times

or in pseudo:

for i from 0 to N
    smallest = MAX_ELEMENT
    foreach b in B
        if bIndex[b] < b.length && b[bIndex[b]] < smallest
            smallest_barrel = b
            smallest = b[bIndex[b]]
    result[i] = smallest
    bIndex[smallest_barrel] += 1

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?