# :: Ord a => [a] -> [a] -package:classy-prelude -package:ghc

The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function. Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input.
```>>> sort [1,6,4,3,2,5]
[1,2,3,4,5,6]
```
The argument must be finite.
The nubOrd function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. By using a Set internally it has better asymptotics than the standard nub function.

#### Strictness

nubOrd is strict in the elements of the list.

#### Efficiency note

When applicable, it is almost always better to use nubInt or nubIntOn instead of this function, although it can be a little worse in certain pathological cases. For example, to nub a list of characters, use
```nubIntOn fromEnum xs
```
Like nub, but has O(n log n) complexity instead of O(n^2). Code for ordNub and listUnion taken from Niklas Hambüchen's ordnub package.
A right-biased version of ordNub. Example:
```>>> ordNub [1,2,1] :: [Int]
[1,2]
```
```>>> ordNubRight [1,2,1] :: [Int]
[2,1]
```
O(n log n). The nubOrd function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. Unlike the standard nub operator, this version requires an Ord instance and consequently runs asymptotically faster.
```nubOrd "this is a test" == "this ae"
nubOrd (take 4 ("this" ++ undefined)) == "this"
\xs -> nubOrd xs == nub xs
```
O(n log n). The nubSort function sorts and removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element.
```nubSort "this is a test" == " aehist"
\xs -> nubSort xs == nub (sort xs)
```
The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function. Elements are arranged from lowest to highest, keeping duplicates in the order they appeared in the input.
```>>> sort [1,6,4,3,2,5]
[1,2,3,4,5,6]
```
Removes duplicate elements from a list, keeping only the first occurance of the element. Like nub but runs in [itex] time and requires Ord.
```>>> ordNub [3, 3, 3, 2, 2, -1, 1]
[3,2,-1,1]
```
Like ordNub runs in [itex] but also sorts a list.
```>>> sortNub [3, 3, 3, 2, 2, -1, 1]
[-1,1,2,3]
```
Strip out duplicates
candidates for Utility ?
On ordered lists, nub is equivalent to nub, except that it runs in linear time instead of quadratic. On unordered lists it also removes elements that are smaller than any preceding element.
```nub [1,1,1,2,2] == [1,2]
nub [2,0,1,3,3] == [2,3]
nub = nubBy (<)
```
The sort function implements a stable sorting algorithm. It is a special case of sortBy, which allows the programmer to supply their own comparison function.
The nubSort function is equivalent to nub . sort, except that duplicates are removed as it sorts. It is essentially the same implementation as Data.List.sort, with merge replaced by union. Thus the performance of nubSort should better than or nearly equal to sort alone. It is faster than both sort and nub . sort when the input contains significant quantities of duplicated elements.
Like nub but runs in O(n * log n) time and requires Ord.
```>>> ordNub [3, 3, 3, 2, 2, -1, 1]
[3,2,-1,1]
```
Like ordNub but also sorts a list.
```>>> sortNub [3, 3, 3, 2, 2, -1, 1]
[-1,1,2,3]
```
O(n log n). Perform a heap sort
Reduce a list of statuses to just one of each status, and if all statuses are present return the empty list.
Remove duplicates but keep elements in order. O(n * log n)
Returns an (arbitrary) representative for each list element that occurs more than once. O(n log n).
Remove the first representative for each list element. Thus, returns all duplicate copies. O(n log n). allDuplicates xs == sort \$ xs \ nub xs.