# Descending sort in Haskell

*April 2, 2016*

When confronted with a problem of sorting a list in descending order in Haskell, it is tempting to reach for a “lazy” solution `reverse . sort`

.

An obvious issue with this is efficiency. While sorting in descending order should in theory be exactly as efficient as sorting in ascending order, the above solution requires an extra list traversal after the sorting itself is done.

This argument can be dismissed on the grounds that `reverse`

’s run time, \(\Theta(n)\), is, in general, less than `sort`

’s run time, \(O(n \log n)\), so it’s not a big deal. Additionally, one could argue that, unlike more complex solutions, this one is “obviously correct”.

As the rest of this article explains, *neither* of these claims holds universally.

## Proper solutions

Here are the two ways to sort a list in descending order that I am aware of. Both require the more general `sortBy`

function

`sortBy :: (a -> a -> Ordering) -> [a] -> [a]`

The first argument to `sortBy`

is the comparison function. For each pair of arguments it returns a value of type

`data Ordering = LT | EQ | GT`

which describes the ordering of those arguments.

The “standard” ordering is given by the `compare`

function from the `Ord`

typeclass. Thus, `sort`

is nothing more than

`sort = sortBy compare`

The first solution to the descending sort problem exploits the fact that, to get the opposite ordering, we can simply swap around the two arguments to `compare`

:

`sortDesc = sortBy (flip compare)`

The second solution relies on the `comparing`

function from `Data.Ord`

, which gives a particular way to compare two values: map them to other values which are then compared using the standard `Ord`

ordering.

`comparing :: Ord a => (b -> a) -> b -> b -> Ordering`

This trick is often used in mathematics: to maximize a function \(x\mapsto f(x)\), it suffices to minimize the function \(x \mapsto -f(x)\). In Haskell, we could write

`sortDesc = sortBy (comparing negate)`

and it would work most of the time. However,

```
> sortDesc [1,minBound::Int]
[-9223372036854775808,1]
```

Besides, negation only works on numbers; what if you want to sort a list of pairs of numbers?

Fortunately, `Data.Ord`

defines a `Down`

newtype which does exactly what we want: it reverses the ordering between values that it’s applied to.

```
> 1 < 2
True
> Down 1 < Down 2
False
```

Thus, the second way to sort the list in descending order is

`sortDesc = sortBy (comparing Down)`

## Asymptotics

Thanks to Haskell’s laziness in general and the careful implementation of `sort`

in particular, `sort`

can run in linear time when only a fixed number of first elements is requested.

So this function will return the 10 largest elements in \(\Theta(n)\) time:

`take 10 . sortBy (comparing Down)`

While our “lazy” solution

`take 10 . reverse . sort`

(which, ironically, turns out not to be lazy enough – in the technical sense of the word “lazy”) will run in \(O(n \log n)\) time. This is because it requests *the last* 10 elements of the sorted list, and in the process of doing so needs to traverse the whole sorted list.

This may appear paradoxical if considered outside of the context of lazy evaluation. Normally, if two linear steps are performed sequentially, the result is still linear. Here we see that adding a linear step upgrades the overall complexity to \(O(n \log n)\).

## Semantics

As I mentioned in the beginning, the simplicity of `reverse . sort`

may be deceptive. The semantics of `reverse . sort`

and `sortBy (comparing Down)`

differ in a subtle way, and you *probably* want the semantics of `sortBy (comparing Down)`

.

This is because `sort`

and `sortBy`

are *stable* sorting functions. They preserve the relative ordering of “equal” elements within the list. Often this doesn’t matter because you cannot tell equal elements apart anyway.

It starts to matter when you use `comparing`

to sort objects by a certain feature. Here we sort the list of pairs by their first elements in descending order:

```
> sortBy (comparing (Down . fst)) [(1,'a'),(2,'b'),(2,'c')]
[(2,'b'),(2,'c'),(1,'a')]
```

According to our criterion, the elements `(2,'b')`

and `(2,'c')`

are considered equal, but we can see that their ordering has been preserved.

The `revese`

-based solution, on the other hand, reverses the order of equal elements, too:

```
> (reverse . sortBy (comparing fst)) [(1,'a'),(2,'b'),(2,'c')]
[(2,'c'),(2,'b'),(1,'a')]
```

Sort with care!

## A note on sorted lists

*Added on 2016-04-03*

The original version of this article said that `sort`

runs in \(\Theta(n \log n)\) time. @obadzz points out that this is not true: `sort`

is implemented in such a way that it will run linearly when the list is already almost sorted in any direction. Thus I have replaced \(\Theta(n \log n)\) with \(O(n \log n)\) when talking about `sort`

’s complexity.