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++)