Algorithms
Sorting (Advanced)
Difficulty: Intermediate
When you call arr.sort() in Python or JavaScript, you are running Timsort, an industrial-strength hybrid that switches between merge sort for long runs and insertion sort for short ones. Sorting a billion elements in seconds is possible...
Sorting (Advanced)
When you call arr.sort() in Python or JavaScript, you are running Timsort, an industrial-strength hybrid that switches between merge sort for long runs and insertion sort for short ones. Sorting a billion elements in seconds is possible only because someone, decades ago, broke the O(n^2) ceiling that bubble sort, selection sort, and insertion sort all sit beneath. This lesson is where you learn how.
Sorting (Advanced) covers the comparison-based O(n log n) algorithms (merge sort, quick sort, heap sort) and the non-comparison sorts (counting sort, radix sort, bucket sort) that beat that bound under structural assumptions about the data. For each you will trace the divide, sort, combine pattern (or its non-recursive equivalent), analyze best, average, and worst case, examine pivot strategies and partitioning schemes for quick sort, and see why heap sort runs in place. The lesson closes with the O(n log n) lower bound for comparison sorting and a quick tour of how built-in sorts (Timsort, V8) blend these techniques.
In Sorting (Elementary), you mastered the vocabulary of passes, swaps, invariants, and stability on O(n^2) algorithms. Recursion Fundamentals gave you the call-stack model that explains the O(log n) factor in merge and quick sort.
Next, Binary Search Templates capitalize on sorted output to solve an entire class of medium-difficulty interview problems.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain how Merge Sort divides, conquers, and merges to achieve O(n log n) time.
Implement Quick Sort with Lomuto partitioning and analyze its best, worst, and average cases.
Describe how Heap Sort uses a max-heap to sort in O(n log n) time and O(1) extra space.
Implement Counting Sort for integer arrays with a known range.
Explain why comparison-based sorts cannot do better than O(n log n) and when non-comparison sorts beat this bound.
Choose the appropriate advanced sort for a given scenario based on data characteristics.
Why This Matters
01
Merge Sort and Quick Sort are the workhorses behind every language's built-in sort: Python uses Timsort (a Merge Sort hybrid), and V8 JavaScript uses Timsort as well.
02
Quick Sort's partitioning technique reappears in Quick Select (find kth element), Dutch National Flag, and many other algorithms.
03
Non-comparison sorts like Counting Sort and Radix Sort beat the O(n log n) lower bound for comparison-based sorting, which is critical when sorting large datasets of bounded integers.
04
Sorting is the prerequisite for binary search, greedy algorithms, and many two-pointer techniques.
Key Terms
7 terms you'll encounter in this lesson
Divide and Conquer
An algorithmic paradigm that breaks a problem into smaller subproblems, solves each recursively, and combines the results. Merge Sort and Quick Sort both use this approach.
Partition
Rearranging an array so that all elements less than a pivot come before it and all elements greater come after it. The core operation in Quick Sort.
Pivot
The element chosen as the reference point for partitioning in Quick Sort. Pivot selection strategy affects worst-case behavior.
Merge
Combining two sorted halves into a single sorted array by comparing elements from each half. The core operation in Merge Sort.
Comparison-based sort
A sorting algorithm that determines order only by comparing pairs of elements. Such algorithms cannot be faster than O(n log n) in the worst case.
Counting Sort
A non-comparison sort that counts occurrences of each value. Runs in O(n + k) time where k is the range of values.
Stable sort
A sort preserving the relative order of equal elements. Merge Sort and Counting Sort are stable; Quick Sort and Heap Sort are not.
Heads Up
Common misconceptions to watch out for
"Quick Sort is always faster than Merge Sort"
Quick Sort has O(n^2) worst case when the pivot is always the smallest or largest element. With random pivots it averages O(n log n) with good constants, but Merge Sort guarantees O(n log n) in all cases. Use Merge Sort when worst-case guarantees matter.
"Counting Sort always runs in O(n) time"
Counting Sort runs in O(n + k) where k is the range of values. If k is much larger than n (e.g., sorting 10 values in the range 0 to 1,000,000), the O(k) term dominates and it becomes impractical.
"Non-comparison sorts are always better than comparison sorts"
Non-comparison sorts only work with specific data types (integers, strings of fixed length). They cannot sort arbitrary objects by a comparison function. Also, their space usage is often O(n + k), higher than in-place comparison sorts.
"Merge Sort uses O(1) extra space"
Standard Merge Sort uses O(n) extra space for the temporary merge buffer. In-place Merge Sort variants exist but are significantly more complex and have higher constant factors.