Algorithms · Hub
Six classic ways to put things in order. Three are simple and run in $O(n^2)$. Three are clever and run in $O(n \log n)$, the best a comparison sort can do.
Why it matters: sorting is the first step of countless other algorithms, such as binary search, deduplication and merging, and it is where you learn the vocabulary of best, worst, stable and in-place.
Answer each one out loud before opening the sample answer.
| Algorithm | Best | Average | Worst | Extra space | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes |
| Insertion | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes |
| Selection | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No | Yes |
| Merge | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | No |
| Quick | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | Yes |
| Heap | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | No | Yes |
Swap neighbours that are out of order until nothing moves.
O(n²) worst · stable · in-place
StudySlide each new item into place inside a growing sorted prefix.
O(n²) worst · O(n) if sorted · stable · in-place
StudyFind the smallest item, put it in front, repeat on the rest.
O(n²) always · not stable · in-place
StudySplit in half, sort each half, merge the two sorted halves.
O(n log n) always · stable · O(n) extra
StudyPartition around a pivot, then sort each side.
O(n log n) avg · O(n²) worst · not stable · in-place
StudyBuild a max-heap, then pull out the maximum n times.
O(n log n) always · not stable · in-place
Study
flowchart TD
A{"Small n (under ~50) or nearly sorted?"} -->|yes| B["Insertion sort"]
A -->|no| C{"Need a stable sort?"}
C -->|yes| D["Merge sort"]
C -->|no| E{"Need a worst-case guarantee with O(1) extra memory?"}
E -->|yes| F["Heap sort"]
E -->|no| G["Quick sort with a random pivot"]
Videos
Come back after 3, 7, 14, then 30 days. Spacing beats cramming.
Explain this topic in your own words, as if teaching a beginner.
Explain it in your own words first, then record a 2–3 minute video on your phone.
25:00
Time's up.
Ready to record? Open your phone camera now and record a 2–3 minute explanation.
Saved only in this browser (localStorage). Nothing is uploaded.