DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

# sort(3C++)

sort -- sort an array in place

## Synopsis

```   template <class T>
void sort(T* b,T* e);
template <class T>
void sort_r(int (*rel)(const T*,const T*),T* b,T* e);
template <class T>
void sort_rs(int (*rel)(const T*,const T*),T* b,T* e);
template <class T>
void sort_s(T* b,T* e);
```

## Assumptions

(1) For the non-relational versions, T::operator< defines a total ordering relation on T.

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

(3) T has operator=.

## Description

These functions sort an array in place.

```   template <class T>
void sort(T* b,T* e);
```

Uses T::operator< to define the ordering relation used by the sorting algorithm sort is not stable; that is, it does not preserve the relative order of equal elements.

```   template <class T>
void sort_r(int (*rel)(const T*,const T*),T* b,T* e);
```

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

```   template <class T>
void sort_rs(int (*rel)(const T*,const T*),T* b,T* e);
```

Like sort_r except that it uses a stable algorithm. That is, the relative order of equal elements is preserved.

```   template <class T>
void sort_s(T* b,T* e);
```

Like sort except that it uses a stable algorithm. That is, the relative order of equal elements is preserved.

## Complexity

If N is the size of the array, then complexity is O(NlgN) on average. Complexity is O(N*N) in the worst case, which is highly improbable.

## Notes

The non-stable versions use drand48(3C) to obtain pseudo-random numbers.

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++)
drand48(3C)
ins_sort(3C++)
merge_sort(3C++)
Block(3C++)
```