Sorting rearranges data into a chosen order. The order may be numeric, lexicographic, or based on a custom key.
Sorting often turns a hard problem into an easier one because nearby values, smallest values, largest values, or ordered boundaries become visible.
Core Idea
Many algorithms become simpler after sorting because they can reason from left to right. Binary search, two pointers, greedy selection, duplicate grouping, and interval processing often depend on sorted order.
Comparison sorting usually has O(n log n) time complexity for efficient general-purpose algorithms.
Sorting is a form of preprocessing. The algorithm pays an upfront cost to create order, then uses that order to answer the real question more easily.
Usage Contract
Python’s sorted(values) accepts an iterable and returns a new sorted list. values.sort() mutates the existing list and returns None.
When sorting records, the key function must return the value that represents the intended order. If original positions matter later, store them before sorting because sorting rearranges the sequence.
Python Example
people = [("Mina", 17), ("Jin", 14), ("Ara", 17)]
by_age = sorted(people, key=lambda person: person[1])sorted returns a new list. list.sort() sorts a list in place.
What Sorting Reveals
After sorting numbers:
values = sorted([7, 2, 9, 3, 2])equal values become adjacent, the smallest value is at the front, the largest value is at the back, and moving left-to-right has a predictable meaning.
This supports common patterns:
- Duplicate detection by comparing neighbors.
- Two pointers from both ends.
- Greedy choice by smallest end time, cost, or deadline.
- Binary search over positions.
Sorting by a Key
Many algorithm problems sort objects by one field:
intervals = [(5, 8), (1, 3), (2, 6)]
intervals.sort(key=lambda interval: interval[1])This sorts intervals by end time. The key should match the reason sorting helps the algorithm.
Cost and Tradeoff
Sorting costs O(n log n) for general comparison sorting. That cost can be worth it if it removes a nested loop or makes many queries easier.
But if one linear scan already solves the problem, sorting may be unnecessary and may lose useful original order.
Common Confusions
Sorting changes the problem structure, but it may also destroy original order. If original positions matter, store them before sorting.
Sorting is not always free. An O(n log n) preprocessing step may be worthwhile for many queries, but unnecessary for a single simple scan.
Sorting by the wrong key can make a greedy algorithm wrong. The order must be justified by the problem’s structure.
When To Use It
Use sorting when relative order reveals useful structure: finding close values, grouping equal values, applying two pointers, choosing cheapest items, or preparing for binary search.
When considering sorting, ask what new fact becomes easy after the data is ordered.
The Main Point
Sorting is preprocessing that creates order. It is worth paying O(n log n) when the new order enables simpler or faster reasoning afterward.