merge(3C++)

Synopsis

   template <class T>    
   void merge(         
      const T* b1, const T* e1,  
      const T* b2, const T* e2, 
      T* b3     
   );     
   template <class T>    
   void merge_r(     
      int (*rel)(const T*, const T*),       
      const T* b1, const T* e1,   
      const T* b2, const T* e2,    
      T* b3    
   );

Assumptions

(1) For the plain version, T::operator< defines a total ordering relation on T and the array is sorted w.r.t. that relation.

(2) For the relational version, rel defines a total ordering relation on T and the array is sorted w.r.t. that relation.

(3) The output array does not overlap either of the two input arrays.

(4) The output array has at least as many cells as both input arrays combined.

(5) T has operator=.

Description

These functions stably combine the elements of two sorted arrays into a new sorted array.

   template <class T>
   void merge(
       const T* b1, const T* e1,
       const T* b2, const T* e2,
       T* b3
       );

Uses T::operator< to define the ordering relation.

   template <class T>
   void merge_r(
       int (*rel)(const T*, const T*),
       const T* b1, const T* e1,
       const T* b2, const T* e2,
       T* b3
       );

Uses rel to define the ordering relation.

Complexity

If N and M are the sizes of the two arrays, then complexity is O(N+M). At most N+M-1 tests of the ordering relation and N+M assignments are done.

Notes

Because a Block (see Block(3C++)) can always be used wherever an array is called for, Array Algorithms can also be used with Blocks. In fact, these two components were actually designed to be used together.

References