Sorting I
**Sorting** means arranging items in order — like alphabetizing a list of names or ordering numbers from smallest to largest. It is one of the most **fundamental operations** in computer science because so many other tasks (searching, finding duplicates, matching data) become much easier once data is sorted. This week you will learn four sorting methods: **Selection Sort** (scan for the smallest, put it first, repeat), **Insertion Sort** (pick each item and slide it into the right place in the already-sorted portion), **Merge Sort** (split the list in half, sort each half, then merge them back together), and **QuickSort** (pick a pivot, partition around it, recurse on both sides). You will also learn the **divide-and-conquer** strategy, how to use the **Master Theorem** to calculate running times of recursive algorithms, a surprising mathematical proof that no comparison-based sorting algorithm can ever do better than $O(n \log n)$ in the worst case, and **Counting Sort** — a non-comparison sort that bypasses this limit.
| Algorithm | Best Case | Average | Worst Case | Stable? | In-place? |
|-----------|-----------|---------|------------|---------|----------|
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | No | Yes |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | Yes | Yes |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | Yes | No ($O(n)$ extra) |
| QuickSort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | No | Yes |
| Counting Sort | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | Yes | No ($O(n+k)$ extra) |
6 topics3 videos1 quiz