# 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