Hey guys,
I am looking for some insight:
Given two sorted arrays of integers A and B, where array B has enough
extra room in it to hold the contents of both A and B. Merge array A
and B together such that the result is the sorted combination of the
two (do not remove duplicates) and the result resides in the B array.
I cannot perform any memory allocations to solve the problem.
Performance considerations should be taken into account in your
solution (so brute force method is not an option). Here is some
example data to help explain:
Array A: 4 7 10 15 17
Array B: 2 4 14 27 X X X X X
Where the X'es are unused slots in array B. The solution would end up
with B looking like this:
Array B: 2 4 4 7 10 14 15 17 27
Using the following function prototype:
void Merge (int *a, int na, int *b, int nb)
Where a and b point to the two arrays, na and nb are the number of
elements in each array. For array b, nb is the number of used
elements, not the size of the array. Assume array b is large enough to
hold the contents of a and b. Using the above example data na would be
5 and nb would be 4.
Also please specify the order of complexity for the algorithm you
chose to solve the problem.
My first thoughts are merge sort of course, although it requires your
to perform additional memory allocation. This leads to me an in
place merge sort.
What do you guys thinks? Any suggestions? Code isn't so important (i
can write that) but I am looking for help with the algorithm.
Thanks!
