I would like to know the complexity (as in O(...) ) of the following sorting algorithm:
- There are B barrels
- that contain a total of N elements, spread unevenly across the barrels.
- The elements in each barrel are already sorted.
The sort 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 the array counter
- increment the last sorted element for the barrel we picked from
- perform those steps N times
or in pseudo code:
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?