Array Merge

[Rinu]

Which is the best algorithm used:
there are two arrays : A sorted in ascending order and B sorted in descending order.
a new array C is made to merge A and B sorted in descending order.

[PanGalactic]

Assuming you mean "vector" rather than "array" (this is a C++ forum after all):

C.reserve(A.size() + B.size());
std::merge(A.begin(), A.end(), B.rbegin(), B.rend(), std::back_inserter(C));
std::reverse(C.begin(), C.end());

[hamsterman]

I'll explain with all arrays sorted in descending order, for simplicity:

C = ...;// allocate an array of A.size + B.size

for(int i = 0, j = 0; i+j < C.size; ){//two counters - one for each array.

   if(j == B.size || i != A.size &&  A[i] > B[j] ) ){
   //move the greater of A[i] and B[j] to the C[i+j], then increase i or j to decrease A[i] or B[j].
   //if j has reached the end of B, you can only move A[i]
   //else if i has reached the end of A, you can only move B[j]

      C[i+j] = A[i];
      i++;
   }else{
      C[i+j] = B[j];
      j++;
   }
}

to make A ascending, replace A[i] with A[A.size-1-i].

[PanGalactic]

hamsterman, am I missing something here? A and B start with a different sort order. How is your merge going to work?

[Rinu]

thanx hamsterman and sry but i didn't understand anything of what PanGalactic said!!

[Rinu]

but isn't the algorithm of jon von neuman different hamsterman?? this one is smaller!!
thanx.

[PanGalactic]

Hi Rinu, the beginner forum will get you answers that go into more detail. This forum is for general C++ questions and assumes one has a fairly solid understanding of the C++ language and the STL.

[Rinu]

sry PanGlactic all i said is that i don't understand it! i am just a beginner maybe what u said is better!! can u explain it to me!!

[hamsterman]

PanGalactic, in the one I wrote, was for when all arrays are descending.

I also wrote:

to make A ascending, replace A[i] with A[A.size-1-i].

That's probably not a good use of word 'make', but whatever..

Rinu, my code and the code from wikipedia work the same way. Only in wikipedia instead of the hard to understand if(j == B.size || i != A.size && A[i] > B[j] ) ) they have several ifs and therefore have to repeat the same lines of code.

[PanGalactic]

Hi Rinu,

C++ provides a standard set of containers for storage and algorithms for doing common tasks. These are part of the Standard Template Library (STL).

Vectors are similar to arrays but they provide more functionality and are less prone to errors. For example, you can query the size of a vector with the size() method. Arrays require one to manage and store that information separately. Vectors can also grow dynamically.

STL containers are accessed via iterators. This is an abstraction that allows one to access different types of containers using a common interface. Iterators model pointers for arrays.

Merging is a common task and the STL provides an algorithm (std::merge) for doing just that. std::merge takes two containers and merges elements in ascending order into a third container.

If you go back to the code I posted, line one just reserves space for the result. It's not necessary because the result vector will grow on its own. It's a small optimization.

Line two merges the two containers into a third. It uses forward iterators for A (which is sorted in ascending order) and reverse iterators for B (reading it in reverse order, because it is in descending order) and uses a back_inserter iterator adapter to append the result to C. The result is a merged result set in ascending order.

The last line reverses the order of C in place (using the STL algorithm std::reverse) to give a result in descending order.

http://www.cplusplus.com/reference/algorithm/merge/
http://www.cplusplus.com/reference/std/iterator/back_inserter/
http://www.cplusplus.com/reference/algorithm/reverse/

You can do this with arrays as well (again, iterators model pointers, so algorithms can work on arrays).

C_size = A_size + B_size;
// Allocate C[C_size]
std::merge(A, A + A_size, std::reverse_iterator(B + B_size - 1), std::reverse_iterator(B - 1), C);
std::reverse(C, C + C_size);

Edit: add code tags.