Sort Lists
Sorting Methods
Python provides two primary ways to sort lists:
- **sorted()**: Returns a new sorted list without modifying the original
- **list.sort()**: Sorts the list in-place and returns None
- Both accept **key** (function) and **reverse** (boolean) parameters
- Sorting is **stable** (maintains relative order of equal elements)
Example
numbers = [3, 1, 4, 1, 5, 9, 2]
# sorted() - returns new list
ascending = sorted(numbers) # [1, 1, 2, 3, 4, 5, 9]
descending = sorted(numbers, reverse=True)
print(ascending)
print(descending)
# sort() - in-place
numbers.sort()
print(numbers)Output
[1, 1, 2, 3, 4, 5, 9] [9, 5, 4, 3, 2, 1, 1] [1, 1, 2, 3, 4, 5, 9]
Custom Sorting
You can sort using **custom key functions** for more advanced sorting needs:
Example
students = [
{'name': 'Alice', 'grade': 92},
{'name': 'Bob', 'grade': 84},
{'name': 'Charlie', 'grade': 90}
]
# Sort by grade (descending)
sorted_students = sorted(students, key=lambda x: x['grade'], reverse=True)
print(sorted_students)
# Case-insensitive string sort
fruits = ['apple', 'Banana', 'cherry']
sorted_fruits = sorted(fruits, key=str.lower)
print(sorted_fruits)Output
[{'name': 'Alice', 'grade': 92}, {'name': 'Charlie', 'grade': 90}, {'name': 'Bob', 'grade': 84}]
['apple', 'Banana', 'cherry']Sorting Algorithms
Python uses the **Timsort** algorithm for sorting, which is a hybrid of merge sort and insertion sort:
- **O(n log n)** worst-case time complexity
- **O(n)** best-case time complexity for nearly sorted data
- **Stable** and efficient for real-world data
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| Timsort (Python's sort) | O(n log n) | O(n) |
| Quicksort | O(n^2) worst, O(n log n) average | O(log n) |
| Merge sort | O(n log n) | O(n) |
| Insertion sort | O(n^2) | O(1) |