.\" ident	@(#)Array_alg:man/ins_sort.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3ins_sort\fP \f3Array_alg(3C++)\fP " "
.SH NAME
ins_sort \- sort an array using an insertion sort algorithm
.SH SYNOPSIS OF Array_alg.h
.Bf

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

.Be
.SH ASSUMPTIONS
.PP
(1) For the plain version, \*(gt\f4::operator<\f1
defines a total ordering relation on \*(gt
.br
(2) For the relational version, \f4rel\f1 defines 
a total ordering relation on \*(gt
.br
(3) \*(gt has \f4operator=\f1
.SH DESCRIPTION
.PP
These functions stably sort an array in place using
an insertion sort algorithm.
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4void ins_sort(\*(gt* b,\*(gt* e);\f1"
Uses \f4\*(gt::operator<\f1 to define the 
ordering relation used by the sorting algorithm.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4void ins_sort_r(int (*rel)(const \*(gt*,const \*(gt*),\*(gt* b,\*(gt* e);\f1"
Uses \f4rel\f1 to define the ordering relation 
used by the sorting algorithm.
.SH COMPLEXITY
.PP
If \f2N\f1 is the size of the array, then 
complexity is \f2O(N*N)\f1.  
On average, \f2N*N/4\f1
tests of the ordering relation and \f2N*N/4\f1
assignments are done.
.SH 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.)
.SH NOTES
Because a Block (see \f3Block(3C++)\f1)
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.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3merge_sort(.)\f1
\f3sort(.)\f1
\f3Block(3C++)\f1
.Be