Extreme Python

Logo

Extremely good python content :)

About

Articles

How to sort in python

by Alan

There are two built-in ways to sort in python: invoking the .sort method on list instances or the global sorted function with an iterable as an argument.

Which one you need depends on whether you want the elements to be sorted in-place and whether you want to sort iterables that are not lists, e.g., tuples. If you’re sorting lists, go with .sort if you want an in-place sort. If you’re not sorting lists, you will need to use .sorted.

Here’s a breakdown of the similarities and differences:

Attribute sort sorted
Stable? Yes Yes
In-place? Yes No
Sorts any iterable? No - list only Yes
Return value None list
Worst case time complexity? O(n log n) O(n log n)
Worst case space complexity? O(n) O(n)
Default sort order Ascending Ascending

Examples

in-place

The .sort method:

>>> numbers = [3, 2, 1]
>>> numbers.sort()
>>> numbers
[1, 2, 3]

numbers.sort() returned nothing and the elements in the list were re-arranged in place.

The sorted function:

>>> numbers = [3, 2, 1]
>>> sorted(numbers)
[1, 2, 3]
>>> numbers
[3, 2, 1]

sorted(numbers) returned a new list and the original array remained unchanged.

Sorting non-lists (other iterables)

The .sort method:

>>> letters = 'cba'
>>> letters.sort()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'str' object has no attribute 'sort'

Woops. .sort is only defined on a list type.

Lets try the sorted function:

>>> letters = 'cba'
>>> sorted(letters)
['a', 'b', 'c']

Voila!

Sorting with a key function

You need to provide a key function if you’re sorting a list of dictionaries or any object that does not support > or < operators.

With .sort:

>>> objects.sort(key=lambda x: x["x"])
>>> objects
[{'x': 1}, {'x': 2}, {'x': 3}]

With sorted:

>>> sorted(objects, key=lambda x: x["x"])
[{'x': 1}, {'x': 2}, {'x': 3}]

Sorting in reverse

Elements are sorted in ascending order, smallest value first, by default. Pass reverse=True to sort by largest value first.

With .sort:

>>> numbers = [2, 1, 3]
>>> numbers.sort(reverse=True)
>>> numbers
[3, 2, 1]

With sorted:

>>> numbers = [2, 1, 3]
>>> sorted(numbers, reverse=True)
[3, 2, 1]

In general, I prefer using sorted unless I absolutely need an in-place sort because it’s more versatile, i.e., can be used on any iterable, and the lack of mutation generally leads to easier to read and less buggy code.

tags: