What is the complexity of this specialized sort
- by ADB
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?
