sort - Maple Programming Help

sort

sort a list of values or a polynomial

 Calling Sequence sort(L) sort(L, output=out) sort(L, >, output=out) sort(L, <, output=out) sort(L, address, output=out) sort(L, length, output=out) sort(L, lexorder, output=out) sort(L, F) sort(L, comptype = F) sort(L, F, output=out) sort(L, comptype = F, output=out) sort(A) sort(A, V, opt) sort(A, order=o, opt) sort[inplace](A)

Parameters

 L - list, Vector, or one-dimensional Array; values to be sorted out - (optional) sorted or permutation or [sorted, permutation] F - (optional) symbol or Boolean function of two arguments; sort ordering A - algebraic; expression to be sorted V - (optional) variables o - (optional) monomial order opt - (optional) either ascending or descending

Description

 • By default, the sort command sorts the elements of a list, Vector, or one-dimensional Array, L, into ascending order and sorts the terms of polynomials in an algebraic expression A into descending order.
 • sort is stable when applied to L. This means that equal elements are ordered by their position in L. In other words, the relative order of equal elements is maintained.
 • If F is given, it specifies the ordering for sorting elements.
 – <:  If F is the symbol < or numeric, then L is sorted in ascending numerical order.  L must contain elements of type({numeric, real_infinity}),
 – >:  If F is the symbol >, then L is sorted into descending numerical order.
 – address:  If F is the symbol address, then the elements are sorted by address (a non-deterministic run-time specific property of the underlying data structure).
 – length:  If F is the symbol length, then the elements are sorted by length where length is as determined by the length function.
 – lexorder:  If F is the symbol lexorder or string, then lists of strings or symbols are sorted into lexicographic order.
 – 'lexorder'[n]:  If L is a list of lists and F is the indexed symbol lexorder[n], where n is a positive integer, then L is sorted into lexicographic order based on the nth element of each sublist of L.
 – Otherwise, F must be a Boolean-valued function of two arguments.  Specifically, $F\left(a,b\right)$ returns $\mathrm{false}$ if and only if $b$ must precede $a$ in the sorted output.  That is $F\left(a,b\right)$ is a non-strict less than comparison function.  In addition, $F\left(a,b\right)$ must be defined for all pairs $a,b$ for $a$ and $b$ in the input structure and $F\left(a,b\right)$ must be transitive, that is, if $F\left(a,b\right)=\mathrm{true}$ and $F\left(b,c\right)=\mathrm{true}$ then $F\left(a,c\right)=\mathrm{true}$.
 • By specifying comptype=F, different styles of comparison functions can be given to sort.  The supported values for comptype are:
 – nonstrict: the comparison function F is a non-strict less than function, as described above.
 – strict: the comparison function F is a strict less than function.  That is $F\left(a,b\right)$ returns $\mathrm{true}$ if and only if $a$ must precede $b$ in the sorted output.  F must still be defined for all pairs of inputs and be transitive, as described above.  This argument is necessary if you want to specify a less than or equal to comparison function and want stable sorting.  Specifying a strict less than function without using the strict option will result in an non-stable, sorted output.
 – key: the function F maps each element in L to a key value.  L is sorted by sorting the corresponding keys.  Using a key function is preferable to a comparison function because the key function is called $\mathrm{O}\left(n\right)$ times, whereas a comparison function will be called $\mathrm{O}\left(n\mathrm{log}\left(n\right)\right)$ times.  This is generally faster.  In addition, sorting the keys may be done in parallel, whereas this may not be possible with a comparison function.
 • If no ordering function F is specified, a list, Vector, or Array with elements of type{numeric, real_infinity} is sorted into increasing numerical order.  The default sorting order when all elements are strings or symbols is lexicographical order. Otherwise, elements of L are sorted by the same rules used to sort sets.  This mixed-element sort is optimized to balance speed and "niceness" of the result.  Data-types of the same structure will be grouped together; within that internal object length is used as the next criteria; further down, individual properties such as numeric order are used when comparing elements during the sort process.
 • If an argument output=permutation is supplied, then sort does not return the sorted argument, but the permutation that would be applied to the argument in order to sort it. The permutation is given as a list of integers: the ith entry of the permutation is the integer j such that the jth entry of L would occur at the ith position in the sorted argument. This means that if $a=\mathrm{sort}\left(L,'\mathrm{output}=\mathrm{permutation}'\right)$ for a list $L$, then $\mathrm{sort}\left(L\right)$ could be obtained as ${L}_{a}$. (For 1-dimensional Arrays A, there may be an offset between the jth entry and the entry obtained as A[j], but the correctly sorted result can be obtained using programmer indexing as $A\left(a\right)$.)
 If an argument output = sorted is supplied, sort returns the sorted argument. This is the default behavior. In order to obtain both the sorted argument and the permutation, one can supply the argument output = [sorted, permutation]. This will return a sequence of two elements, the first being the sorted argument, the second the permutation.
 • In Maple, polynomials are not automatically stored in sorted order. They are stored in the order they were first created and printed in the order they are stored. The sort command can be used to sort polynomials.
 Note: Sorting polynomials is a destructive operation: the input polynomial is sorted "in-place".
 • If V is given, it specifies the variable ordering to be used when sorting polynomials. It can be a name, a function, or a list or set of names (for the multivariate case).
 All polynomials in the expression A are sorted into decreasing order in V. If V is a list or set then polynomials in V are sorted in total degree with ties broken by lexicographic order (this is called graded lexicographic order). If neither V nor o is specified then the indets appearing in A and graded lexicographic order are used.
 • Other monomial orders can be specified by using the order=o calling sequence. The supported orders are:
 plex(x1, ..., xn) - lexicographic order
 grlex(x1, ..., xn) - graded lexicographic order
 tdeg(x1, ..., xn) - graded reverse lexicographic order
 for indeterminates x1, ..., xn. For a description of these orders, see Monomial orders for multivariate polynomials.
 • When sorting polynomials the optional argument ascending or descending may be specified to put the terms into ascending or descending order, respectively. The default is descending order, which puts higher-degree terms before lower-degree terms.
 • The sorting algorithm used for sorting lists is a recursive implementation of Merge sort with early detection of sorted sequences. The sorting algorithm used for sorting polynomials is an in-place Shell sort. Lexicographic ordering of strings and symbols assumes the collating sequence of the US-ASCII character set.
 • When called using the indexed name, sort['inplace'], the command will attempt to sort the given Array or Vector in-place.  If the first argument is not a mutable data structure, such as a list, then the sorting will be done in a copy.

 • The sort command is thread safe as of Maple 15, provided that a polynomial is not being sorted.  Sorting polynomials is not thread safe.

Examples

 > $\mathrm{sort}\left(\left[2,1,3\right]\right)$
 $\left[{1}{,}{2}{,}{3}\right]$ (1)
 > $\mathrm{sort}\left(\left[2,1,3\right],\mathrm{numeric}\right)$
 $\left[{1}{,}{2}{,}{3}\right]$ (2)
 > $\mathrm{sort}\left(\left[2,1,3\right],\mathrm{>}\right)$
 $\left[{3}{,}{2}{,}{1}\right]$ (3)
 > $\mathrm{sort}\left(1+x+{x}^{2}\right)$
 ${{x}}^{{2}}{+}{x}{+}{1}$ (4)
 > $\mathrm{sort}\left(\left[c,a,d\right],\mathrm{lexorder}\right)$
 $\left[{a}{,}{c}{,}{d}\right]$ (5)
 > $\mathrm{sort}\left(\left[a,\mathrm{ba},\mathrm{aaa},\mathrm{aa}\right],\mathrm{length}\right)$
 $\left[{a}{,}{\mathrm{ba}}{,}{\mathrm{aa}}{,}{\mathrm{aaa}}\right]$ (6)
 > $\mathrm{sort}\left(\left[a,\mathrm{ax},\mathrm{bb},\mathrm{bf}\right],\mathrm{address}\right)$
 $\left[{\mathrm{ax}}{,}{\mathrm{bb}}{,}{\mathrm{bf}}{,}{a}\right]$ (7)
 > $\mathrm{z1}≔\left["three","four","two"\right]$
 ${\mathrm{z1}}{:=}\left[{"three"}{,}{"four"}{,}{"two"}\right]$ (8)
 > $\mathrm{z2}≔\left[3,4,2\right]$
 ${\mathrm{z2}}{:=}\left[{3}{,}{4}{,}{2}\right]$ (9)
 > $\mathrm{permutation}≔\mathrm{sort}\left(\mathrm{z2},'\mathrm{output}=\mathrm{permutation}'\right)$
 ${\mathrm{permutation}}{:=}\left[{3}{,}{1}{,}{2}\right]$ (10)
 > ${\mathrm{z1}}_{\mathrm{permutation}}$
 $\left[{"two"}{,}{"three"}{,}{"four"}\right]$ (11)
 > $\mathrm{z3}≔⟨"five","eight","two","four"⟩$
 ${\mathrm{z3}}{:=}\left[\begin{array}{c}{"five"}\\ {"eight"}\\ {"two"}\\ {"four"}\end{array}\right]$ (12)
 > $\mathrm{z4}≔\mathrm{Array}\left(\left[5,8,2,4\right]\right)$
 ${\mathrm{z4}}{:=}\left[\begin{array}{cccc}{5}& {8}& {2}& {4}\end{array}\right]$ (13)
 > $\mathrm{result},\mathrm{permutation2}≔\mathrm{sort}\left(\mathrm{z4},'\mathrm{output}=\left[\mathrm{sorted},\mathrm{permutation}\right]'\right)$
 ${\mathrm{result}}{,}{\mathrm{permutation2}}{:=}\left[\begin{array}{cccc}{2}& {4}& {5}& {8}\end{array}\right]{,}\left[{3}{,}{4}{,}{1}{,}{2}\right]$ (14)
 > $\mathrm{result}$
 $\left[\begin{array}{cccc}{2}& {4}& {5}& {8}\end{array}\right]$ (15)
 > ${\mathrm{z3}}_{\mathrm{permutation2}}$
 $\left[\begin{array}{c}{"two"}\\ {"four"}\\ {"five"}\\ {"eight"}\end{array}\right]$ (16)
 > $f≔4{x}^{3}+5{x}^{2}{z}^{2}+2x{y}^{2}z+1$
 ${f}{:=}{5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{4}{}{{x}}^{{3}}{+}{1}$ (17)
 > $\mathrm{sort}\left(f,\left[x,y,z\right]\right)$
 ${5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{4}{}{{x}}^{{3}}{+}{1}$ (18)
 > $\mathrm{sort}\left(f,\left[x,y,z\right],\mathrm{ascending}\right)$
 ${1}{+}{4}{}{{x}}^{{3}}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{5}{}{{x}}^{{2}}{}{{z}}^{{2}}$ (19)
 > $\mathrm{sort}\left(f,\mathrm{order}=\mathrm{grlex}\left(x,y,z\right)\right)$
 ${5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{4}{}{{x}}^{{3}}{+}{1}$ (20)
 > $\mathrm{sort}\left(f,\mathrm{order}=\mathrm{tdeg}\left(x,y,z\right)\right)$
 ${2}{}{x}{}{{y}}^{{2}}{}{z}{+}{5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{4}{}{{x}}^{{3}}{+}{1}$ (21)
 > $\mathrm{sort}\left(f,\mathrm{order}=\mathrm{plex}\left(x,y,z\right)\right)$
 ${4}{}{{x}}^{{3}}{+}{5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{1}$ (22)
 > $\mathrm{sort}\left(f,\mathrm{order}=\mathrm{plex}\left(x,y,z\right),\mathrm{descending}\right)$
 ${4}{}{{x}}^{{3}}{+}{5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{1}$ (23)
 > $\mathrm{sort}\left(f,\mathrm{order}=\mathrm{plex}\left(x,y,z\right),\mathrm{ascending}\right)$
 ${1}{+}{2}{}{x}{}{{y}}^{{2}}{}{z}{+}{5}{}{{x}}^{{2}}{}{{z}}^{{2}}{+}{4}{}{{x}}^{{3}}$ (24)
 > $\mathrm{sort}\left(\frac{y+x}{y-x},x\right)$
 $\frac{{x}{+}{y}}{{-}{x}{+}{y}}$ (25)
 > $\mathrm{sort}\left(ax+by+c{x}^{2},x\right)$
 ${c}{}{{x}}^{{2}}{+}{a}{}{x}{+}{b}{}{y}$ (26)
 > $\mathrm{sort}\left(ax+by+c{x}^{2},x,\mathrm{ascending}\right)$
 ${b}{}{y}{+}{a}{}{x}{+}{c}{}{{x}}^{{2}}$ (27)

The powers in an algebraic expression do not have to be positive integers. They can be negative integers or fractions.

 > $f≔\frac{a}{{x}^{2}}+\frac{b}{{x}^{6}}+\frac{c}{{x}^{4}}+\frac{d}{{x}^{\frac{3}{2}}}$
 ${f}{:=}\frac{{a}}{{{x}}^{{2}}}{+}\frac{{b}}{{{x}}^{{6}}}{+}\frac{{c}}{{{x}}^{{4}}}{+}\frac{{d}}{{{x}}^{{3}{/}{2}}}$ (28)
 > $\mathrm{sort}\left(f,x\right)$
 $\frac{{d}}{{{x}}^{{3}{/}{2}}}{+}\frac{{a}}{{{x}}^{{2}}}{+}\frac{{c}}{{{x}}^{{4}}}{+}\frac{{b}}{{{x}}^{{6}}}$ (29)
 > $l≔\mathrm{LibraryTools}:-\mathrm{ShowContents}\left(\right):$
 > $\mathrm{sl}≔\mathrm{sort}\left(l,{\mathrm{lexorder}}_{1}\right):$
 > ${\mathrm{sl}}_{1..10}$
 $\left[\left[{"#msup\left(mi\left("a"\right),mo\left("+"\right)\right).m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{45}{,}{39}\right]{,}{103712227}{,}{43}\right]{,}\left[{"#msup\left(mi\left("a"\right),mo\left("-"\right)\right).m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{45}{,}{39}\right]{,}{27703968}{,}{46}\right]{,}\left[{"%?.m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{36}{,}{55}\right]{,}{32819229}{,}{35}\right]{,}\left[{"%T.m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{36}{,}{55}\right]{,}{66626485}{,}{35}\right]{,}\left[{"\infty .m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{47}{,}{36}\right]{,}{40745794}{,}{36}\right]{,}\left[{"&where.m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{42}{,}{7}\right]{,}{39161678}{,}{385}\right]{,}\left[{"-.m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{42}{,}{30}\right]{,}{103141265}{,}{182}\right]{,}\left[{"....m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{36}{,}{56}\right]{,}{46575444}{,}{36}\right]{,}\left[{"..m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{37}{,}{4}\right]{,}{24853033}{,}{1702}\right]{,}\left[{"/.m"}{,}\left[{2016}{,}{2}{,}{16}{,}{22}{,}{42}{,}{30}\right]{,}{34833978}{,}{182}\right]\right]$ (30)

An example of stable sorting.  Sort based on the first element in the sublist. Notice that sublists whose first elements are equal are ordered based on their position in the input list.

 > $\mathrm{sort}\left(\left[\left[1,1\right],\left[2,1\right],\left[3,1\right],\left[1,2\right],\left[2,2\right],\left[3,2\right],\left[1,3\right],\left[2,3\right],\left[3,3\right]\right],\left(x,y\right)→{x}_{1}\le {y}_{1}\right)$
 $\left[\left[{1}{,}{1}\right]{,}\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{2}{,}{1}\right]{,}\left[{2}{,}{2}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{1}\right]{,}\left[{3}{,}{2}\right]{,}\left[{3}{,}{3}\right]\right]$ (31)

Specifying the strict option allows the use of a strict less than comparison function while still producing stable sorting.

 > $\mathrm{sort}\left(\left[\left[1,1\right],\left[2,1\right],\left[3,1\right],\left[1,2\right],\left[2,2\right],\left[3,2\right],\left[1,3\right],\left[2,3\right],\left[3,3\right]\right],\mathrm{strict}=\left(\left(x,y\right)→{x}_{1}<{y}_{1}\right)\right)$
 $\left[\left[{1}{,}{1}\right]{,}\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{2}{,}{1}\right]{,}\left[{2}{,}{2}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{1}\right]{,}\left[{3}{,}{2}\right]{,}\left[{3}{,}{3}\right]\right]$ (32)

This example could also be sorted using the key option.

 > $\mathrm{sort}\left(\left[\left[1,1\right],\left[2,1\right],\left[3,1\right],\left[1,2\right],\left[2,2\right],\left[3,2\right],\left[1,3\right],\left[2,3\right],\left[3,3\right]\right],\mathrm{key}=\left(x→{x}_{1}\right)\right)$
 $\left[\left[{1}{,}{1}\right]{,}\left[{1}{,}{2}\right]{,}\left[{1}{,}{3}\right]{,}\left[{2}{,}{1}\right]{,}\left[{2}{,}{2}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{1}\right]{,}\left[{3}{,}{2}\right]{,}\left[{3}{,}{3}\right]\right]$ (33)

This example sorts a Vector in-place.  Notice that myVec is changed after calling sort

 > $\mathrm{myVec}≔⟨2,1,4⟩$
 ${\mathrm{myVec}}{:=}\left[\begin{array}{r}{2}\\ {1}\\ {4}\end{array}\right]$ (34)
 > $\mathrm{sort}['\mathrm{inplace}']\left(\mathrm{myVec}\right)$
 $\left[\begin{array}{r}{1}\\ {2}\\ {4}\end{array}\right]$ (35)
 > $\mathrm{myVec}$
 $\left[\begin{array}{r}{1}\\ {2}\\ {4}\end{array}\right]$ (36)

This example ignores the inplace option because it is given a non-mutable list to sort.  Notice that myList is *not* changed after calling sort

 > $\mathrm{myList}≔\left[2,1,4\right]$
 ${\mathrm{myList}}{:=}\left[{2}{,}{1}{,}{4}\right]$ (37)
 > $\mathrm{sort}\left(\mathrm{myList}\right)$
 $\left[{1}{,}{2}{,}{4}\right]$ (38)
 > $\mathrm{myList}$
 $\left[{2}{,}{1}{,}{4}\right]$ (39)

Compatibility

 • The output option was introduced in Maple 17.
 • The comptype option was updated in Maple 18.
 • The sort command was updated in Maple 2016.
 • The inplace option was introduced in Maple 2016.