Importance of sorting algorighms. What sorting methods exists
Sorting algorithms are methods used to arrange data in a specific order (usually ascending or descending).
Let's look into the classical problem statement:
Given a list of elements, rearrange them so that (or in descending order).
A valid solution must:
Sorting is a foundational tool in computer science and appears in many real tasks:
Before looking at classical algorithms, it is important to know that Python already has highly optimized sorting built in. In practice and in competitive programming, you will use these almost exclusively:
Both .sort() and sorted() are based on Timsort — an algorithm that is fast, stable, and battle-tested. Use these in every real problem.
Beyond the three simple algorithms in this module, there exist efficient sorting algorithms — Merge Sort, Quick Sort, Heap Sort — that all run in . This is a dramatic improvement over : for , the difference is roughly 10,000,000,000 operations vs 1,700,000 operations.
It is actually possible to prove mathematically that no comparison-based sorting algorithm can do better than in the worst case. If your algorithm can only learn about the data by comparing pairs of elements, then is the theoretical lower bound — you cannot beat it.
However, there are exceptions. Counting Sort and Radix Sort avoid direct comparisons entirely — they exploit the structure of the values (e.g., integers in a known range) to sort in . They work differently from all comparison-based algorithms and are not constrained by the same lower bound. The trade-off is that they only work for specific types of data and require extra memory. These are advanced topics covered in later courses.
The three algorithms in the following lessons — Bubble Sort, Selection Sort, and Insertion Sort — are all and too slow for large inputs. We study them not because you will use them directly, but because their underlying ideas are genuinely useful in competitive programming.
For example:
Understanding these algorithms builds intuition for reasoning about order, comparisons, and swaps — skills that show up constantly in harder problems.
a = [5, 3, 8, 1, 9, 2]
# Sort in place — modifies the list directly
a.sort()
print(a) # [1, 2, 3, 5, 8, 9]
# Return a new sorted list — original unchanged
b = [5, 3, 8, 1, 9, 2]
c = sorted(b)
print(b) # [5, 3, 8, 1, 9, 2] — unchanged
print(c) # [1, 2, 3, 5, 8, 9]
# Descending order
a.sort(reverse=True)
print(a) # [9, 8, 5, 3, 2, 1]
# Sort by custom key
words = ["banana", "apple", "cherry", "fig"]
words.sort(key=len)
print(words) # ['fig', 'apple', 'banana', 'cherry']
pairs = [(1, 5), (3, 2), (2, 8)]
pairs.sort(key=lambda p: p[1]) # sort by second element
print(pairs) # [(3, 2), (1, 5), (2, 8)]