Overview
EasyWhy sorting matters · stability · in-place
Sorting means putting things in order, like lining up your class from shortest to tallest so everything after is easier.
The idea
Sorting arranges data so later work (searching, deduping, greedy sweeps) becomes easy. Key properties: time complexity, whether it's in-place (O(1) extra memory), and whether it's stable (keeps equal elements' order).
The trick
- Comparison sorts can't beat O(n log n) in the worst case.
- Merge sort is stable & O(n log n); quicksort is in-place & fast in practice.
5
2
8
1
0
1
2
3
Step 1 of 16. Sorting means putting things in order — smallest to biggest. Let's sort these four numbers. Values: 5, 2, 8, 1.
1/16
Optimal
timeO(n log n)spaceO(1)–O(n)
Pick by constraints.
1Bubble / Selection / Insertion O(n²) simple2Merge sort O(n log n) stable3Quick sort O(n log n) in-place4Built-in sort() O(n log n)Input
- array
- [5, 2, 8, 1]
Output
- sorted
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- [5, 1, 4, 2] with bubble sort
- Output:
- [1, 2, 4, 5] after 3 passes
- Explanation:
- Each pass floats the largest remaining value to the end. Simple, stable, and O(n²) — fine for teaching, not for n = 100000.
Example 2
- Input:
- [5, 1, 4, 2] with merge sort
- Output:
- [1, 2, 4, 5] in O(n log n)
- Explanation:
- Split to [5,1] and [4,2], sort each, then zip. Stable, but it needs a second array — the in-place-versus-fast trade the chapter is about.
Finished the walkthrough? Add it to your streak.