# Sorting Mini-HOW TO

**Original version by Andrew Dalke**

Python lists have a built-in `sort()` method. There are many ways to use it to sort a list and there doesn't appear to be a single, central place in the various manuals describing them, so I'll do so here.

## Sorting basic data types

A simple ascending sort is easy; just call the `sort()` method of a list.

>>> a = [5, 2, 3, 1, 4] >>> a.sort() >>> print a [1, 2, 3, 4, 5]

Sort takes an optional function which can be called for doing the comparisons. The default sort routine is equivalent to:

>>> a = [5, 2, 3, 1, 4] >>> a.sort(cmp) >>> print a [1, 2, 3, 4, 5]

where `cmp()` is the built-in function that compares two objects, `x` and `y`, and returns a negative number, 0 or a positive number depending on whether x<y, x==y, or x>y. During the course of the sort the relationships must stay the same for the final list to make sense.

If you want, you can define your own function for the comparison. For integers (and numbers in general) we can do:

>>> def numeric_compare(x, y): >>> return x-y >>>

Or, more verbosely, but a little more understandable:

>>> def numeric_compare(x, y): >>> if x>y: >>> return 1 >>> elif x==y: >>> return 0 >>> else: # x<y >>> return -1 >>> >>> a = [5, 2, 3, 1, 4] >>> a.sort(numeric_compare) >>> print a [1, 2, 3, 4, 5]

By the way, the short function won't work if the result of the subtraction is out of range, as in `sys.maxint - (-1)`.

Or, if you don't want to define a new named function you can create an anonymous one using `lambda`, as in:

>>> a = [5, 2, 3, 1, 4] >>> a.sort(lambda x, y: x-y) >>> print a [1, 2, 3, 4, 5]

Python 2.4 adds three keyword arguments to `sort()` that simplify many common usages: `cmp`, `key`, and `reverse`. The `cmp` keyword is for providing a sorting function; the previous examples could be written as:

>>> a.sort(cmp=numeric_compare) >>> a.sort(cmp=lambda x,y: x-y)

The `reverse` parameter is a Boolean value; if it's true, the list is sorted into reverse order.

>>> a = [5, 2, 3, 1, 4] >>> a.sort(reverse=True) >>> a [5, 4, 3, 2, 1]

For Python versions before 2.4, you can reverse the sense of the comparison function:

>>> a = [5, 2, 3, 1, 4] >>> def reverse_numeric(x, y): >>> return y-x >>> >>> a.sort(reverse_numeric) >>> a [5, 4, 3, 2, 1]

(a more general implementation could return `cmp(y,x)` or `-cmp(x,y)`).

However, it's faster if Python doesn't have to call a function for every comparison, so the most efficient solution is to do the forward sort first, then use the `reverse()` method.

>>> a = [5, 2, 3, 1, 4] >>> a.sort() >>> a.reverse() >>> a [5, 4, 3, 2, 1]

## Sorting by keys

Python 2.4's `key` parameter lets you derive a sorting key for each element of the list, and then sort using the key.

For example, here's a case-insensitive string comparison:

>>> a = "This is a test string from Andrew".split() >>> a.sort(key=str.lower) >>> a ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']

The value of the `key` parameter should be a function that takes a single argument and returns a key to use for sorting purposes.

Often there's a built-in that will match your needs, such as `string.lower()`. The `operator` module contains a number of functions useful for this purpose. For example, you can sort tuples based on their second element using `operator.itemgetter()`:

{{{>>> import operator >>> L = [('c', 2), ('d', 1), ('a', 4), ('b', 3)] >>> map(operator.itemgetter(0), L) ['c', 'd', 'a', 'b'] >>> map(operator.itemgetter(1), L) [2, 1, 4, 3] >>> sorted(L, key=operator.itemgetter(1)) [('d', 1), ('c', 2), ('b', 3), ('a', 4)] }}}

Versions of Python before 2.4 don't have the convenient `key` parameter of `sort()`, so you have to write a comparison function that embodies the key-generating logic: