|
|
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);
(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.
(M) T has operator=.
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.
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.
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.