Week 39 of 43
CP Track
WEEK 39 LEARNING MODULE
Advanced Sorting: Divide & Conquer and Non-Comparison Sorting
Covers advanced sorting algorithms: Merge Sort ($O(n \log n)$ stable), Quick Sort ($O(n \log n)$ avg, in-place), Quickselect ($O(n)$ avg), Radix Sort, Bucket Sort, and linked list sorting.
7 Practice Problems4 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Master advanced Divide & Conquer sorts: Merge Sort ($O(n \log n)$ stable) and Quick Sort ($O(n \log n)$ average).
- ✓Implement Quickselect to find the $k$-th smallest/largest element in $O(n)$ average time without full sorting.
- ✓Implement non-comparison linear sorts: Radix Sort ($O(d \cdot (n + k))$) and Bucket Sort ($O(n)$ average).
- ✓Sort Singly Linked Lists in $O(n \log n)$ time and $O(\log n)$ space using Merge Sort.
- ✓Analyze stability, pivot selection strategies (Randomized / Median-of-Three), and worst-case safeguards.
Core Concepts
Merge Sort & Subarray Merging
O(n log n) time, O(n) spaceRecursively dividing array in half, sorting halves, and merging two sorted subarrays in O(n) linear time.
Quick Sort & Partitioning Schemes
O(n log n) avg, O(n²) worstPartitioning array around a pivot such that elements < pivot are on left and > pivot on right.
Quickselect ($k$-th Order Statistic)
O(n) average timePartitioning only the half containing index k to find k-th element in linear average time.
Non-Comparison Sorting (Radix & Bucket Sort)
O(d * (n + k)) or O(n)Sorting by processing digit-by-digit or distributing elements into buckets.
Algorithms Covered
Merge Sort ($O(n \log n)$)Quick Sort & 3-Way PartitioningQuickselect ($O(n)$ avg)Linked List Merge SortRadix SortBucket Sort
Data Structures Applied
ArraysLinked Lists
“The first law of success is concentration — to bend all the energies to one point, and to go directly to that point, looking neither to the right nor to the left.”
— William Matthews