sorted() and Sorting

The sorted() function returns a new sorted list from any iterable. Understanding sorting keys and custom comparisons is essential for data manipulation.

---

Basic Usage

sorted() Returns New List

numbers = [3, 1, 4, 1, 5, 9, 2, 6]
result = sorted(numbers)

print(result)   # [1, 1, 2, 3, 4, 5, 6, 9]
print(numbers)  # [3, 1, 4, 1, 5, 9, 2, 6] (unchanged)

Works on Any Iterable

# Strings
sorted("python")           # ['h', 'n', 'o', 'p', 't', 'y']

# Tuples
sorted((3, 1, 2))          # [1, 2, 3]

# Sets
sorted({3, 1, 2})          # [1, 2, 3]

# Dictionaries (sorts keys)
sorted({'c': 3, 'a': 1})   # ['a', 'c']

# Generators
sorted(x**2 for x in [3, 1, 2])  # [1, 4, 9]

---

sorted() vs list.sort()

Feature	sorted()	list.sort()
Returns	New list	None (in-place)
Works on	Any iterable	Lists only
Original	Unchanged	Modified
Memory	Creates copy	No extra memory

# sorted() - creates new list
original = [3, 1, 2]
new_list = sorted(original)
print(original)  # [3, 1, 2] (unchanged)

# list.sort() - modifies in place
original = [3, 1, 2]
result = original.sort()
print(result)    # None
print(original)  # [1, 2, 3] (modified)

---

Reverse Sorting

numbers = [3, 1, 4, 1, 5]

# Descending order
sorted(numbers, reverse=True)  # [5, 4, 3, 1, 1]

# Also works with list.sort()
numbers.sort(reverse=True)

---

The key Parameter

The key parameter specifies a function to extract a comparison key from each element.

Sort by Length

words = ['banana', 'pie', 'apple', 'fig']

sorted(words, key=len)
# ['pie', 'fig', 'apple', 'banana']

Sort Case-Insensitive

names = ['Bob', 'alice', 'Charlie', 'david']

# Default: uppercase before lowercase
sorted(names)              # ['Bob', 'Charlie', 'alice', 'david']

# Case-insensitive
sorted(names, key=str.lower)  # ['alice', 'Bob', 'Charlie', 'david']

Sort by Absolute Value

numbers = [-5, 2, -1, 4, -3]

sorted(numbers, key=abs)   # [-1, 2, -3, 4, -5]

Sort with Lambda

pairs = [(1, 'b'), (3, 'a'), (2, 'c')]

# Sort by second element
sorted(pairs, key=lambda x: x[1])
# [(3, 'a'), (1, 'b'), (2, 'c')]

# Sort by first element (default behavior)
sorted(pairs, key=lambda x: x[0])
# [(1, 'b'), (2, 'c'), (3, 'a')]

---

Sorting Dictionaries

Sort by Keys

scores = {'Bob': 85, 'Alice': 92, 'Charlie': 78}

# Sorted keys
sorted(scores)                    # ['Alice', 'Bob', 'Charlie']

# Sorted items by key
sorted(scores.items())            # [('Alice', 92), ('Bob', 85), ('Charlie', 78)]

Sort by Values

scores = {'Bob': 85, 'Alice': 92, 'Charlie': 78}

# Sort by value (ascending)
sorted(scores.items(), key=lambda x: x[1])
# [('Charlie', 78), ('Bob', 85), ('Alice', 92)]

# Sort by value (descending)
sorted(scores.items(), key=lambda x: x[1], reverse=True)
# [('Alice', 92), ('Bob', 85), ('Charlie', 78)]

Create Sorted Dictionary (Python 3.7+)

scores = {'Bob': 85, 'Alice': 92, 'Charlie': 78}

sorted_dict = dict(sorted(scores.items(), key=lambda x: x[1]))
# {'Charlie': 78, 'Bob': 85, 'Alice': 92}

---

Sorting Objects

Using Attributes

class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age

    def __repr__(self):
        return f"Student({self.name}, {self.grade})"

students = [
    Student('Alice', 85, 20),
    Student('Bob', 92, 19),
    Student('Charlie', 85, 21),
]

# Sort by grade
sorted(students, key=lambda s: s.grade)
# [Student(Alice, 85), Student(Charlie, 85), Student(Bob, 92)]

# Sort by name
sorted(students, key=lambda s: s.name)
# [Student(Alice, 85), Student(Bob, 92), Student(Charlie, 85)]

Using operator.attrgetter

from operator import attrgetter

# Cleaner than lambda for attribute access
sorted(students, key=attrgetter('grade'))
sorted(students, key=attrgetter('name'))

# Multiple attributes
sorted(students, key=attrgetter('grade', 'age'))

Using operator.itemgetter

from operator import itemgetter

# For dictionaries or tuples
records = [
    {'name': 'Alice', 'score': 85},
    {'name': 'Bob', 'score': 92},
]

sorted(records, key=itemgetter('score'))
# [{'name': 'Alice', 'score': 85}, {'name': 'Bob', 'score': 92}]

# For tuples
pairs = [(1, 'b'), (3, 'a'), (2, 'c')]
sorted(pairs, key=itemgetter(1))  # [(3, 'a'), (1, 'b'), (2, 'c')]

---

Multi-Key Sorting

Using Tuples

students = [
    ('Alice', 85),
    ('Bob', 92),
    ('Charlie', 85),
]

# Sort by grade, then by name
sorted(students, key=lambda x: (x[1], x[0]))
# [('Alice', 85), ('Charlie', 85), ('Bob', 92)]

# Sort by grade descending, name ascending
sorted(students, key=lambda x: (-x[1], x[0]))
# [('Bob', 92), ('Alice', 85), ('Charlie', 85)]

Multiple Sorts (Stable Sort)

Python's sort is stable—equal elements keep their relative order. Use this for multi-key sorting:

students = [
    ('Alice', 85),
    ('Bob', 92),
    ('Charlie', 85),
]

# Sort by name first, then by grade
# (because stable sort preserves order of equal elements)
result = sorted(students, key=lambda x: x[0])  # by name
result = sorted(result, key=lambda x: x[1])    # by grade

# Result: [('Alice', 85), ('Charlie', 85), ('Bob', 92)]

---

Special Cases

Sorting None Values

data = [3, None, 1, None, 2]

# This fails!
# sorted(data)  # TypeError: '<' not supported between 'int' and 'NoneType'

# Put None values at end
sorted(data, key=lambda x: (x is None, x))
# [1, 2, 3, None, None]

# Put None values at beginning
sorted(data, key=lambda x: (x is not None, x))
# [None, None, 1, 2, 3]

Sorting Mixed Types (Python 3)

# Python 3 doesn't allow mixed type comparison
mixed = [1, 'a', 2, 'b']
# sorted(mixed)  # TypeError

# Convert to common type
sorted(mixed, key=str)  # [1, 2, 'a', 'b']

Natural Sorting (Numeric Strings)

files = ['file1.txt', 'file10.txt', 'file2.txt', 'file20.txt']

# Default: lexicographic (wrong for numbers)
sorted(files)
# ['file1.txt', 'file10.txt', 'file2.txt', 'file20.txt']

# Natural sort
import re
def natural_key(s):
    return [int(c) if c.isdigit() else c.lower() 
            for c in re.split(r'(\d+)', s)]

sorted(files, key=natural_key)
# ['file1.txt', 'file2.txt', 'file10.txt', 'file20.txt']

---

Performance

Time Complexity

• Best case: O(n) — already sorted
• Average/Worst case: O(n log n)
• Space: O(n) for sorted(), O(1) for list.sort()

Tips

# Avoid sorting repeatedly
data = [...]
sorted_data = sorted(data)  # Sort once, use many times

# Use key functions efficiently
# Good: simple attribute access
sorted(items, key=lambda x: x.value)

# Bad: expensive computation in key
sorted(items, key=lambda x: expensive_function(x))

# Better: precompute if sorting repeatedly
decorated = [(expensive_function(x), x) for x in items]
decorated.sort()
result = [x for _, x in decorated]

---

Summary

Task	Code
Basic sort	sorted(items)
Reverse	sorted(items, reverse=True)
By length	sorted(items, key=len)
Case-insensitive	sorted(items, key=str.lower)
By attribute	sorted(items, key=attrgetter('attr'))
By dict key	sorted(items, key=itemgetter('key'))
Multi-key	sorted(items, key=lambda x: (x.a, x.b))
Descending + ascending	sorted(items, key=lambda x: (-x.a, x.b))

Key Takeaways:

• sorted() returns a new list; list.sort() modifies in place
• Use key parameter for custom sort orders
• operator.attrgetter and itemgetter are cleaner than lambdas
• Python's sort is stable—use for multi-key sorting
• Use tuple keys for multiple sort criteria
• Negate numeric values for mixed ascending/descending sorts