# Python sort list

Python sort list tutorial shows how to sort list elements in Python language.

## Sorting

In computer science, sorting is arranging elements in an ordered sequence. Over the years, several algorithms were developed to perform sorting on data, including merge sort, quick sort, selection sort, or bubble sort. (The other meaning of sorting is categorizing; it is grouping elements with similar properties.)

The opposite of sorting, rearranging a sequence of elements in a random or meaningless order, is called shuffling.

Data can be sorted alphabetically or numerically. The sort key specifies the criteria used to perform the sort. It is possible to sort objects by multiple keys. For instance, when sorting users, the names of the users could be used as primary sort key, and their occupation as the secondary sort key.

## Sorting order

A standard order is called the ascending order: a to z, 0 to 9. The reverse order is called the descending order: z to a, 9 to 0. For dates and times, ascending means that earlier values precede later ones e.g. 1/1/2020 will sort ahead of 1/1/2021.

## Stable sort

A stable sort is one where the initial order of equal elements is preserved. Some sorting algorithms are naturally stable, some are unstable. For instance, the merge sort and the bubble sort are stable sorting algorithms. On the other hand, heap sort and quick sort are examples of unstable sorting algorithms.

Consider the following values: `3715593`. A stable sorting produces the following: `1335579`. The ordering of the values 3 and 5 is kept. An unstable sorting may produce the following: `1335579`.

Python uses the timsort algorithm. It is a hybrid stable sorting algorithm, derived from merge sort and insertion sort. It was implemented by Tim Peters in 2002 for use in the Python programming language.

## Python sort functions

Python has two basic function for sorting lists: `sort` and `sorted`. The `sort` sorts the list in place, while the `sorted` returns a new sorted list from the items in iterable. Both functions have the same options: `key` and `reverse`. The `key` takes a function which will be used on each value in the list being sorted to determine the resulting order. The `reverse` option can reverse the comparison order.

Both functions produce stable sorting.

## Python sort list in-place

The `sort` function of the list container modifies the original list when doing the sorting.

inplace_sort.py
```#!/usr/bin/env python3

words = ['forest', 'wood', 'tool', 'arc', 'sky', 'poor', 'cloud', 'rock']
vals = [2, 1, 0, 3, 4, 6, 5, 7]

words.sort()
print(words)

vals.sort()
print(vals)
```

In the example, we sort the list of strings and integers. The original lists are modified.

```\$ ./inplace_sort.py
['arc', 'cloud', 'forest', 'poor', 'rock', 'sky', 'tool', 'wood']
[0, 1, 2, 3, 4, 5, 6, 7]
```

This is the output.

## Python sorted example

The `sorted` function does not modify the original list; rather, it creates a new modified list.

sorted_fun.py
```#!/usr/bin/env python3

words = ['forest', 'wood', 'brisk', 'tree', 'sky', 'cloud', 'rock', 'falcon']

sorted_words = sorted(words)
print('Original:', words)
print('Sorted:', sorted_words)
```

The example creates a new sorted list of words from the original list, which is intact.

```\$ ./sorted_fun.py
Original: ['forest', 'wood', 'brisk', 'tree', 'sky', 'cloud', 'rock', 'falcon']
Sorted: ['brisk', 'cloud', 'falcon', 'forest', 'rock', 'sky', 'tree', 'wood']
```

This is the output.

## Python sort list in ascending/descending order

The ascending/descending order is `controlled` with the `reverse` option.

asc_desc.py
```#!/usr/bin/env python3

words = ['forest', 'wood', 'tool', 'arc', 'sky', 'poor', 'cloud', 'rock']

words.sort()
print(words)

words.sort(reverse=True)
print(words)
```

The example sorts the list of words in ascending and descending order.

```\$ ./asc_desc.py
['arc', 'cloud', 'forest', 'poor', 'rock', 'sky', 'tool', 'wood']
['wood', 'tool', 'sky', 'rock', 'poor', 'forest', 'cloud', 'arc']
```

This is the output.

## Python sort list of dates

In the next example, we sort a list of dates.

sort_date.py
```#!/usr/bin/env python3

from datetime import datetime

values = ['8-Nov-19', '21-Jun-16', '1-Nov-18', '7-Apr-19']
values.sort(key=lambda d: datetime.strptime(d, "%d-%b-%y"))

print(values)
```

The anonymous function uses the `strptime` function, which creates a datetime object from the given string. Effectively, the `sort` function sorts datetime objects.

If you are not familiar with the lambda keyword, learn more about anonymous functions in Python lambda tutorial.

```\$. /sort_date.py
['21-Jun-16', '1-Nov-18', '7-Apr-19', '8-Nov-19']
```

This is the output.

## Python sort list by element index

A Python list can have nested iterables. In such cases, we can choose the elements which should be sorted.

sort_elem_idx.py
```#!/usr/bin/env python3

vals = [(4, 0), (0, -2), (3, 5), (1, 1), (-1, 3)]

vals.sort()
print(vals)

vals.sort(key=lambda e: e[1])
print(vals)
```

The example sorts the nested tuples initally by their first elements, then by their second.

```vals.sort(key=lambda e: e[1])
```

By providing an anonymous function which returns the second element of the tuple, we sort the tuples by their second values.

```\$ ./sort_elem_idx.py
[(-1, 3), (0, -2), (1, 1), (3, 5), (4, 0)]
[(0, -2), (4, 0), (1, 1), (-1, 3), (3, 5)]
```

This is the output.

## Python sort list by sum of nested list

Say we have nested lists which all have some various rankings. The final ranking is the sum of all the values.

sort_sum.py
```#!/usr/bin/env python3

data = [[10, 11, 12, 13], [9, 10, 11, 12], [8, 9, 10, 11], [10, 9, 8, 7],
[6, 7, 8, 9], [5, 5, 5, 1], [5, 5, 5, 5], [3, 4, 5, 6], [10, 1, 1, 2]]

data.sort()
print(data)

data.sort(key=sum)
print(data)
```

By default, the sorting functions sort by the first value of the nested lists. To achieve our goal, we pass the built-in `sum` function to the `key` option.

```\$ ./sort_sum.py
[[3, 4, 5, 6], [5, 5, 5, 1], [5, 5, 5, 5], [6, 7, 8, 9], [8, 9, 10, 11], [9, 10, 11, 12], [10, 1, 1, 2], [10, 9, 8, 7], [10, 11, 12, 13]]
[[10, 1, 1, 2], [5, 5, 5, 1], [3, 4, 5, 6], [5, 5, 5, 5], [6, 7, 8, 9], [10, 9, 8, 7], [8, 9, 10, 11], [9, 10, 11, 12], [10, 11, 12, 13]]
```

The example shows the default and the custom sorting.

## Python sort list of localized strings

For locale aware sorting, we can use the `locale.strxfrm()` for the key function.

locale_sort.py
```#!/usr/bin/env python3

import locale

words = ['zem', 'čučoriedka', 'drevo', 'štebot', 'cesta', 'černice', 'ďateľ',
'rum', 'železo', 'prameň', 'sob']
locale.setlocale(locale.LC_COLLATE, ('sk_SK', 'UTF8'))

words.sort(key=locale.strxfrm)

for word in words:
print (word)
```

The example sorts Slovak words.

```\$ ./locale_sort.py
cesta
černice
čučoriedka
ďateľ
drevo
prameň
rum
sob
štebot
zem
železo
```

This is the output.

Note: the resulting order of the Slovak words is not entirely correct. The letter ď goes after d. It depends on how well the language is supported.

## Python sort list of dictionaries

When sorting dictionaries, we can choose the property by which the sorting is performed.

sort_dict.py
```#!/usr/bin/env python3

users = [
{'name': 'John Doe', 'date_of_birth': 1987},
{'name': 'Jane Doe', 'date_of_birth': 1996},
{'name': 'Robert Brown', 'date_of_birth': 1977},
{'name': 'Lucia Smith', 'date_of_birth': 2002},
{'name': 'Patrick Dempsey', 'date_of_birth': 1994}
]

users.sort(reverse=True, key=lambda e: e['date_of_birth'])

for user in users:
print(user)
```

We have a list of users. Each user is represented by a dictionary.

```users.sort(reverse=True, key=lambda e: e['date_of_birth'])
```

In the anonymous function, we choose the `date_of_birth` property.

```\$ ./sort_dict.py
{'name': 'Lucia Smith', 'date_of_birth': 2002}
{'name': 'Jane Doe', 'date_of_birth': 1996}
{'name': 'Patrick Dempsey', 'date_of_birth': 1994}
{'name': 'John Doe', 'date_of_birth': 1987}
{'name': 'Robert Brown', 'date_of_birth': 1977}
```

The users are sorted by their date of birth in descending order.

## Python sort list of grades

There are various grading systems around the world. Our example contains grades such as A+ or C- and these cannot be ordered lexicographically. We use a dictionary where each grade has its given value.

```#!/usr/bin/env python3

data = 'A+ A A- B+ B B- C+ C C- D+ D'

def mc(e):

students = [('Anna', 'A+'), ('Jozef', 'B'), ('Rebecca', 'B-'), ('Michael', 'D+'),
('Zoltan', 'A-'), ('Jan', 'A'), ('Michelle', 'C-'), ('Sofia', 'C+')]

students.sort(key=mc)
print(students)

# from operator import itemgetter
```

We have a list of students. Each student has a name and a grade in a nested tuple.

```data = 'A+ A A- B+ B B- C+ C C- D+ D'
```

We build the dictionary of grades. Each grade has its value. The grades will be sorted by their dictionary value.

```def mc(e):
```

The key function simply returns the value of the grade.

```# from operator import itemgetter
```

This solution uses an anonymous function.

```\$ ./grades.py
{'A+': 0, 'A': 1, 'A-': 2, 'B+': 3, 'B': 4, 'B-': 5, 'C+': 6, 'C': 7, 'C-': 8, 'D+': 9, 'D': 10}
[('Anna', 'A+'), ('Jan', 'A'), ('Zoltan', 'A-'), ('Jozef', 'B'), ('Rebecca', 'B-'), ('Sofia', 'C+'), ('Michelle', 'C-'), ('Michael', 'D+')]
```

This is the output.

## Python sort list by string length

Sometimes, we need to sort the strings by their length.

sort_by_len.py
```#!/usr/bin/env python3

def w_len(e):
return len(e)

words = ['forest', 'wood', 'tool', 'sky', 'poor', 'cloud', 'rock', 'if']

words.sort(reverse=True, key=w_len)

print(words)
```

In this example, we do not use an anonymous function.

```def w_len(e):
return len(e)
```

The `w_len` function returns the length of each of the elements.

```\$ ./sort_by_len.py
['forest', 'cloud', 'wood', 'tool', 'poor', 'rock', 'sky', 'if']
```

The words are ordered by their length in descending order.

## Python sort list by case

By default, the strings with uppercase first letters are sorted before the other strings. We can sort strings regardless of their case as well.

case_sorting.py
```#!/usr/bin/env python3

text = 'Today is a beautiful day. Andy went fishing.'
words = text.replace('.', '')

sorted_words = sorted(words.split(), key=str.lower)
print('Case insensitive:', sorted_words)

sorted_words2 = sorted(words.split())
print('Case sensitive:', sorted_words2)
```

By providing the `str.lower` function to the key attribute, we perform a case insensitive sorting.

```\$ ./case_sorting.py
Case insensitive: ['a', 'Andy', 'beautiful', 'day', 'fishing', 'is', 'Today', 'went']
Case sensitive: ['Andy', 'Today', 'a', 'beautiful', 'day', 'fishing', 'is', 'went']
```

This is the output.

## Python sort list by lastname

In the following example, we sort the names by last name.

sort_by_lastname.py
```#!/usr/bin/env python3

names = ['John Doe', 'Jane Doe', 'Robert Brown', 'Robert Novak',
'Lucia Smith', 'Patrick Dempsey', 'George Marshall', 'Alan Brooke',
'Harold Andras', 'Albert Doe']

names.sort()
names.sort(key=lambda e: e.split()[-1])

for name in names:
print(name)
```

We have a list of names. Each name consists of a first name and last name. In addition, there are several users with the same last name. In such a case, we want them to be sorted by their first names.

```names.sort()
names.sort(key=lambda e: e.split()[-1])
```

First, we sort the names by their first names. Then we sort the names by their last name. To do so, we split each string and choose the last string (it has index -1.) Since Python's sort algorithm is stable, the first sorting is remembered and we get the expected output.

```\$ ./sort_by_lastname.py
Harold Andras
Alan Brooke
Robert Brown
Patrick Dempsey
Albert Doe
Jane Doe
John Doe
George Marshall
Robert Novak
Lucia Smith
```

The names are sorted by their last names. The Doe users are correctly sorted by their first names.

## Python sort list of namedtuples

In the next example, we sort namedtuples.

namedtuple_sort.py
```#!/usr/bin/env python3

from typing import NamedTuple

class City(NamedTuple):
id: int
name: str
population: int

c1 = City(1, 'Bratislava', 432000)
c2 = City(2, 'Budapest', 1759000)
c3 = City(3, 'Prague', 1280000)
c4 = City(4, 'Warsaw', 1748000)
c5 = City(5, 'Los Angeles', 3971000)
c6 = City(6, 'Edinburgh', 464000)
c7 = City(7, 'Berlin', 3671000)

cities = [c1, c2, c3, c4, c5, c6, c7]

cities.sort(key=lambda e: e.name)

for city in cities:
print(city)
```

The `City` namedtuple has three attributes: `id`, `name`, and `population`. The example sorts the namedtuples by their names.

```cities.sort(key=lambda e: e.name)
```

The anonymous function returns the name property of the namedtuple.

```\$ ./namedtuple_sort.py
City(id=7, name='Berlin', population=3671000)
City(id=1, name='Bratislava', population=432000)
City(id=2, name='Budapest', population=1759000)
City(id=6, name='Edinburgh', population=464000)
City(id=5, name='Los Angeles', population=3971000)
City(id=3, name='Prague', population=1280000)
City(id=4, name='Warsaw', population=1748000)
```

This is the output.

## Python sort list by multiple sort criteria

The following example sorts a list of students by two sorting criteria.

multiple_sort.py
```#!/usr/bin/env python3

from typing import NamedTuple
from operator import attrgetter

def multi_sort(data, specs):

for key, reverse in reversed(specs):
data.sort(key=attrgetter(key), reverse=reverse)
return data

class Student(NamedTuple):
id: int
name: str
age: int

s1 = Student(1, 'Patrick', 'A', 21)
s2 = Student(2, 'Lucia', 'B', 19)
s3 = Student(3, 'Robert', 'C', 19)
s4 = Student(4, 'Monika', 'A', 22)
s5 = Student(5, 'Thomas', 'D', 20)
s6 = Student(6, 'Petra', 'B', 18)
s6 = Student(7, 'Sofia', 'A', 18)
s7 = Student(8, 'Harold', 'E', 22)
s8 = Student(9, 'Arnold', 'B', 23)

students = [s1, s2, s3, s4, s5, s6, s7, s8]

for student in students:
print(student)
```

First, the students are sorted by grades in ascending order, then they are sorted by age in descending order.

```def multi_sort(data, specs):

for key, reverse in reversed(specs):
data.sort(key=attrgetter(key), reverse=reverse)
return data
```

The `multi_sort` method applies all the sorting specs on the list.

```\$ ./multi_sort.py
```

This is the output.

## Python sort list of custom complex objects - bags of coins

We have a custom object, a namedtuple, which has a specific way to sort it.

Note: According to the Python documentation, the `sort` and `sorted` use only the `__lt__` magic method when doing sorting. So we need to implement only this method. However, the PEP8 recommends to implement all six operations (`__eq__` , `__ne__` , `__lt__` , `__le__` , `__gt__`, `__ge__`) for safety and code completeness.

The `total_ordering` decorator from the `functools` module helps to reduce the boilerplate. The `total_ordering` requires the `__eq__` and one of the remaining methods to be implemented.

sort_coins.py
```#!/usr/bin/env python3

from typing import NamedTuple
from functools import total_ordering

# a gold coin equals to two silver and six bronze coins

class Coin(NamedTuple):

rank: str

@total_ordering
class Pouch:

def __init__(self):
self.bag = []

self.bag.append(coin)

def __eq__(self, other):

val1, val2 = self.__evaluate(other)

if val1 == val2:
return True
else:
return False

def __lt__(self, other):

val1, val2 = self.__evaluate(other)

if val1 < val2:
return True
else:
return False

def __str__(self):

return f'Pouch with: {self.bag}'

def __evaluate(self, other):

val1 = 0
val2 = 0

for coin in self.bag:

if coin.rank == 'g':
val1 += 6

if coin.rank == 's':
val1 += 3

if coin.rank == 'b':
val1 += 1

for coin in other.bag:

if coin.rank == 'g':
val2 += 6

if coin.rank == 's':
val2 += 3

if coin.rank == 'b':
val2 += 1

return val1, val2

def create_pouches():

p1 = Pouch()

p2 = Pouch()

p3 = Pouch()

p4 = Pouch()

p5 = Pouch()

p6 = Pouch()

p7 = Pouch()

p8 = Pouch()

bag = [p1, p2, p3, p4, p5, p6, p7, p8]

return bag

bag = create_pouches()
bag.sort()

for e in bag:
print(e)
```

In the example, we sort pouches of coins. There are three types of coins: gold, silver, and bronze. One gold coin equals to two silver and six bronze coins. (Therefore, one silver coin equals to three bronze coins.)

```class Coin(NamedTuple):

rank: str
```

Our custom object is a namedtuple, which has one attribute: `rank`.

```@total_ordering
class Pouch:

def __init__(self):
self.bag = []

self.bag.append(coin)
...
```

The `Pouch` has an internal `self.bag` list for storing its coins. In the class, we have two comparison methods: `__lt__` and `__eq__`. The `@total_ordering` decorator supplies the rest.

```def __lt__(self, other):

val1, val2 = self.__evaluate(other)

if val1 < val2:
return True
else:
return False
```

The `__lt__` method is used by the Python sorting functions to compare two objects. We have to compute the value of all coins in two pouches and compare them.

```def __str__(self):

return f'Pouch with: {self.bag}'
```

The `__str__` gives the human-readable representation of the `Pouch` object.

```def __evaluate(self, other):

val1 = 0
val2 = 0

for coin in self.bag:

if coin.rank == 'g':
val1 += 6

if coin.rank == 's':
val1 += 3

if coin.rank == 'b':
val1 += 1

for coin in other.bag:

if coin.rank == 'g':
val2 += 6

if coin.rank == 's':
val2 += 3

if coin.rank == 'b':
val2 += 1

return val1, val2
```

The `__evaluate` method calculates the values of the two pouches. It returns both values to the `__lt__` for comparison.

```def create_pouches():

p1 = Pouch()

p2 = Pouch()

...
```

In the `create_pouches` function we create eight pouches with various amounts of coins.

```bag.sort()

for e in bag:
print(e)
```

We sort the bag of pouches and then print the elements of the sorted bag.

```\$ ./coins.py
Pouch with: [Coin(rank='b'), Coin(rank='s')]
Pouch with: [Coin(rank='b'), Coin(rank='b'), Coin(rank='b'), Coin(rank='b'), Coin(rank='b')]
Pouch with: [Coin(rank='g')]
Pouch with: [Coin(rank='b'), Coin(rank='s'), Coin(rank='s')]
Pouch with: [Coin(rank='g'), Coin(rank='s')]
Pouch with: [Coin(rank='g'), Coin(rank='b'), Coin(rank='s')]
Pouch with: [Coin(rank='g'), Coin(rank='s'), Coin(rank='s'), Coin(rank='b'), Coin(rank='b'), Coin(rank='b')]
Pouch with: [Coin(rank='g'), Coin(rank='g'), Coin(rank='s')]
```

This is the output. The pouch with two gold coins and one silver coin is the most valuable.

In this tutorial, we have covered sorting operations on lists in Python.

List all Python tutorials.