Introduction to sorting

Sorting algorithms are methods used to arrange data in a specific order. An overview of where sorting appears, Python's built-in sort, the O(N log N) lower bound, and why classical algorithms are worth studying.

Where Sorting Is Helpful

Sorting is a foundational tool in computer science and appears in many real tasks:

• Binary search requires sorted data
• Many dynamic programming and greedy algorithms sort first
• Ranking students by scores
• Detecting duplicates (after sorting, equal items are adjacent)
• Sorting points by x-coordinate
• Sorting edges by weight (e.g., Kruskal's MST algorithm)
• Sorting tasks by deadlines or durations

Python's Built-in Sorting

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 $O(N \log N)$ algorithm that is fast, stable, and battle-tested. Use these in every real problem.

Efficient Sorting Algorithms

Beyond the three simple algorithms in this module, there exist efficient sorting algorithms — Merge Sort, Quick Sort, Heap Sort — that all run in $O(N \log N)$. This is a dramatic improvement over : for , the difference is roughly 10,000,000,000 operations vs 1,700,000 operations.