DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK

# ins_sort(3C++)

ins_sort -- sort an array using an insertion sort algorithm

## Synopsis

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

## 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) T has operator=.

## Description

These functions stably sort an array in place using an insertion sort algorithm.

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

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

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

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(N*N). On average, N*N/4 tests of the ordering relation and N*N/4 assignments are done.

## Notes

Insertion sorting is the algorithm of choice when either: 1) the size of the array is small; OR 2) the number of elements out of order is small; OR 3) the average distance between the original position of an element and its final destination is small. (By "small" we mean less than 16.)

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++), merge_sort(3C++), sort(3C++), Block(3C++)