DSA TrainerFoundations · Unit 15
Sorting
Sorting feels too basic to think about. You call .sort() and move on. But two things make it worth a unit. First, the obvious way to sort, comparing everything to everything, is slow enough to choke on large input, and understanding why is a clean lesson in complexity. Second, sorting is a setup move: a huge number of problems get easy the moment the data is in order.
The naive sorts you might invent on your own (compare each pair, swap when out of order) run in O(n squared). The sorts your language actually uses run in O(n log n), and the gap between those is the difference between code that scales and code that stalls.
This unit shows why the naive approach is slow, how the divide-and-conquer trick behind merge sort gets to O(n log n), and, most usefully, what sorted data lets you do that unsorted data does not.
You’re not signed in. Your progress here won’t be saved.
Why the obvious way is slow
If you sort by hand the naive way, you compare elements and swap the ones out of order, passing over the list again and again until nothing is out of place. That is roughly what bubble sort and selection sort do.
The problem is the comparisons. To be sure the list is sorted, each element ends up compared against many others, and that "many others" grows with the list. For n elements you do on the order of n times n comparisons. That is O(n squared): double the input and the work quadruples. On a million elements it is hopeless.
A naive sort compares elements against each other in a nested-loop fashion (each against many others). What is its time complexity?
The drills and graded test are premium
The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:
- ✓2 applied drills: train spotting when the concept applies
- ✓A 5-question graded test to clear the unit
- ✓The full guided problem ladder with faded hints, plus the cold-read capstone
From $6/month. Cancel anytime.