Sorting Algorithms: Let A and B be two linear arrays. How to merge these two arrays into a new array C?

As Oscar pointed out,  the question is if each are sorted already. If not, I'd sort each one separately ,to think of the counter way of doing it, merge, then sort, you can see it would have higher complexity. That is: length(A) + length(B) =  length(C) O(N) of a good sort is usually O(nlogn) unless there are specific properties that allow for something like counting sort etc.  1- Sorting each first will give: O(N) of A = O(length(A)*log(length(A)) O(N) of B = O(length(B)*log(length(B)) Now that you have a 2 sorted arrays, create an array C of length A+B (obviously). I'd prefer not to write out the algorithm, Oscar has already, in words I'd think of 2 decks of cards with random numbers on them, sorted top to bottom. In a loop, until *one* of the decks A or B runs out of cards: - You will look at the top of each deck, the lower number gets moved to C. At one point, one of the decks will exhaust first, you can they simply move (arraycopy) the remainder of that deck to C, this is because those are already sorted.  You'll notice some interesting properties. 1- If the numbers are pretty well intermixed, you reach n² comparisons. 2- If the numbers mostly are disjoint, as in most of B is larger than A or the reverse, this procedure gets closer to O(n) as you can consider the array copy as a constant time operation ( or even iteratively , O(n)).