DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 

merge_sort(3C++)


merge_sort -- stably sort an array

Synopsis

   template <class T>    
   T* merge_sort(T* b1,T* e1,T* b2);     
   template <class T>    
   T* merge_sort_r(int (*rel)(const T*,const T*),               
       T* b1,T* e1,T* b2);

Assumptions

(1) For the plain version, T::operator< defines a total ordering relation on T.

(2) For the relational version, rel defines a total ordering relation on T.

(3) The two arrays do not overlap.

(4) The second array has at least as many cells as the first array.

(5) T has operator=.

Description

These functions stably sort an array using a merge sorting algorithm. The algorithm requires an auxiliary array of the same size, identified by the argument b2. They return a pointer to either (1) the original array or (2) the auxiliary array, depending on which one contains the final result of the sort.

   template <class T>
   T* merge_sort(T* b1,T* e1,T* b2);

Uses T::operator< to define the ordering relation used by the sorting algorithm.

   template <class T>
   T* merge_sort_r(int (*rel)(const T*,const T*),
       T* b1,T* e1,T* b2);

Uses rel to define the ordering relation used by the sorting algorithm.

Complexity

If N is the size of the array, then complexity is O(NlgN). At most NlgN tests of the ordering relation and NlgN 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

Array_alg(3C++), ins_sort(3C++), sort(3C++), Block(3C++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004