Number of comparisons of putting a sorted array of size $n$ into $k$ boxes Suppose I have an array of numbers with size $n$, denoted as $A$ and the numbers inside have already been sorted from smallest to largest. I have $k$ boxes, and $k<n$. For each box, there is a number, called splitter. Suppose the splitter of box $i$ is smaller than that of $j$, if $i<j$. Denote $B$ is an array whose $i$-the element is for the splitter of box $i$ and we have $B[i]<B[j]$ if $i<j$.
I want to put the numbers of the array into the boxes in the following way. If $A[0]<B[0]$, we put $A[0]$ into box 1, and compare with $A[1]$ and $B[0]$. If $A[0]>B[0]$, we then compare $A[0]$ and $B[1]$ and repeat the procedure above, until we put all the number into the box. If there is a $i$ such that $A[i] > B[k]$. We then leave those elements in $A$.
Then how many comparisons in total for this process. Is it $\mathcal{O}(n+k)$?
Many thanks
 A: The number of comparisons is not just $O(n+k)$: it's at most $n+k-1$. 
To see that's the case, call a box "full" as soon as you find an element that is larger than the splitter of the box (which means no more elements will go into the box). Then note that, every time you compare an element to the splitter of the current box either the element is smaller, in which case you put it into the box, or it is larger, in which case you declare the box full. In either case, you have "eliminated" either a box or an element. Since you start with $k$ boxes and $n$ elements, and you end up either with at least $1$ non-full box (if some splitter was larger than every element) or with at least $1$ un-boxed element (if at least one element was larger than every splitter), you can perform no more than $n+k-1$ comparisons. 
It's also easy to see that in some cases you perform exactly $n+k-1$ comparisons: e.g. if all elements are smaller than the largest splitter, but larger than every other splitter, you perform $k$ comparisons on the first element, and $1$ comparison on each of the remaining $n-1$ elements.
