\Header{sort}{Sorting or Ordering Vectors}
\alias{is.unsorted}{sort}
\keyword{univar}{sort}
\keyword{manip}{sort}
\keyword{arith}{sort}
\begin{Description}\relax
Sort (or \emph{order}) a numeric or complex vector (partially) into
ascending (or descending) order.\end{Description}
\begin{Usage}
\begin{verbatim}
sort(x, partial = NULL, na.last = NA, decreasing = FALSE,
     method = c("shell", "quick"), index.return = FALSE)
is.unsorted(x, na.rm = FALSE)
\end{verbatim}
\end{Usage}
\begin{Arguments}
\begin{ldescription}
\item[\code{x}] a numeric or complex vector.
\item[\code{partial}] a vector of indices for partial sorting.
\item[\code{na.last}] for controlling the treatment of \code{NA}s.
If \code{TRUE}, missing values in the data are put last; if
\code{FALSE}, they are put first; if \code{NA}, they are removed.
\item[\code{decreasing}] logical.  Should the sort be increasing or decreasing?
\item[\code{method}] character specifying the algorithm used.
\item[\code{index.return}] logical indicating if the ordering index vector should
be returned as well; this is only available for the default
\code{na.last = NA}.
\item[\code{na.rm}] logical.  Should missing values be removed?
\end{ldescription}
\end{Arguments}
\begin{Details}\relax
If \code{partial} is not \code{NULL}, it is taken to contain indices
of elements of \code{x} which are to be placed in their correct
positions by partial sorting.  After the sort, the values specified in
\code{partial} are in their correct position in the sorted array.  Any
values smaller than these values are guaranteed to have a smaller
index in the sorted array and any values which are greater are
guaranteed to have a bigger index in the sorted array.

The sort order for character vectors will depend on the collating
sequence of the locale in use: see \code{\Link{Comparison}}.

\code{is.unsorted} returns a logical indicating if \code{x} is sorted
increasingly, i.e., \code{is.unsorted(x)} is true if \code{any(x !=
    sort(x))} (and there are no \code{NA}s).

\code{method = "shell"} uses Shellsort (an \eqn{O(n^{4/3})}{} variant
from Sedgewick (1996)).  If \code{x} has names a stable sort is used,
so ties are not reordered.  (This only matters if names are present.)

Method \code{"quick"} uses Singleton's Quicksort implementation and is
only available when \code{x} is numeric (double or integer) and
\code{partial} is \code{NULL}.  It is normally somewhat faster than
Shellsort (perhaps twice as fast on vectors of length a million) but
has poor performance in the rare worst case.
(Peto's modification using a pseudo-random midpoint is used to make
the worst case rarer.)  This is not a stable sort, and ties may be
reordered.\end{Details}
\begin{Value}
For \code{sort} the sorted vector unless
\code{index.return} is true, when the result is
a list with components named \code{x} and \code{ix} containing the
sorted numbers and the ordering index vector.  In the latter case,
if \code{method == "quick"} ties may be reversed in the ordering,
unlike \code{sort.list}, as quicksort is not stable.\end{Value}
\begin{References}\relax
Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988)
\emph{The New S Language}.
Wadsworth \& Brooks/Cole.

Sedgewick, R. (1986)
A new upper bound for Shell sort.
\emph{J. Algorithms} \bold{7}, 159--173.

Singleton, R. C. (1969) An efficient algorithm for sorting with
minimal storage: Algorithm 347.
\emph{Communications of the ACM} \bold{12}, 185--187.\end{References}
\begin{SeeAlso}\relax
\code{\Link{order}}, \code{\Link{rank}}.\end{SeeAlso}
\begin{Examples}
\begin{ExampleCode}
data(swiss)
x <- swiss$Education[1:25]
x; sort(x); sort(x, partial = c(10, 15))
median # shows you another example for 'partial'

## illustrate 'stable' sorting (of ties):
sort(c(10:3,2:12), method = "sh", index=TRUE) # is stable
## $x : 2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10 10 11 12
## $ix: 9  8 10  7 11  6 12  5 13  4 14  3 15  2 16  1 17 18 19
sort(c(10:3,2:12), method = "qu", index=TRUE) # is not
## $x : 2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10 10 11 12
## $ix: 9 10  8  7 11  6 12  5 13  4 14  3 15 16  2 17  1 18 19
##        ^^^^^

## Don't run: ## Small speed comparison simulation:
N <- 2000
Sim <- 20
rep <- 50 # << adjust to your CPU
c1 <- c2 <- numeric(Sim)
for(is in 1:Sim){
  x <- rnorm(N)
  gc()  ## sort should not have to pay for gc
  c1[is] <- system.time(for(i in 1:rep) sort(x, method = "shell"))[1]
  c2[is] <- system.time(for(i in 1:rep) sort(x, method = "quick"))[1]
  stopifnot(sort(x, meth = "s") == sort(x, meth = "q"))
}
100 * rbind(ShellSort = c1, QuickSort = c2)
cat("Speedup factor of quick sort():\n")
summary({qq <- c1 / c2; qq[is.finite(qq)]})

## A larger test
x <- rnorm(1e6)
gc()
system.time(x1 <- sort(x, method = "shell"))
gc()
system.time(x2 <- sort(x, method = "quick"))
stopifnot(identical(x1, x2))
## End Don't run\end{ExampleCode}
\end{Examples}

