Comparison-Based Sorting

Sorting is the most studied problem in computer science, and for good reason - it appears everywhere, from database indexing to rendering graphics. This article takes you deep into the four most important comparison-based sorting algorithms: QuickSort, MergeSort, HeapSort, and TimSort (Java's default).

Understanding these algorithms at the implementation level transforms how you think about data processing and gives you the tools to make informed decisions in production systems.

📋 At a Glance

Algorithm	Time (Avg)	Time (Worst)	Space	Stable	In-Place
QuickSort	O(n log n)	O(n²)	O(log n)	No	Yes
MergeSort	O(n log n)	O(n log n)	O(n)	Yes	No
HeapSort	O(n log n)	O(n log n)	O(1)	No	Yes
TimSort	O(n log n)	O(n log n)	O(n)	Yes	No

🎯 What You'll Learn

After reading this article, you will be able to:

Implement QuickSort with multiple pivot strategies and 3-way partitioning
Understand MergeSort's stability and why it matters for complex objects
Build HeapSort from scratch using the heapify operation
Explain TimSort's hybrid approach and why Java chose it
Prove the Ω(n log n) lower bound for comparison-based sorting
Choose the right algorithm based on data characteristics

🔥 Production Story: The Sorted Data Disaster

An e-commerce platform had a product listing service that sorted items by price. Performance was excellent in testing with random data. In production, disaster struck.

JAVA(6 lines)
Code
Loading syntax highlighter...

What happened:

The product database was already mostly sorted by price (products added in price tiers). When users filtered by category, results came back nearly sorted.

TEXT(2 lines)
Code
Loading syntax highlighter...

The investigation revealed:

Before Java 7, Arrays.sort() for objects used MergeSort. But for primitives, it used QuickSort with a fixed pivot strategy. A developer had converted Product prices to a primitive array for "optimization":

JAVA(11 lines)
Code
Loading syntax highlighter...

With first-element pivot on sorted data, QuickSort degrades to O(n²).

The fix:

JAVA(6 lines)
Code
Loading syntax highlighter...

Result: TimSort recognized the nearly-sorted pattern and completed in 15ms.

The lesson: Algorithm choice matters. QuickSort's O(n²) worst case isn't theoretical - it happens with real data patterns. Know your data.

🧠 Mental Model: The Sorting Spectrum

Think of sorting algorithms on a spectrum of trade-offs:

TEXT(33 lines)
Code
Loading syntax highlighter...

Stability matters when:

Sorting objects by multiple fields
Preserving previous sort order
User expectations (stable sorts feel "less random")

🎮 Try It Yourself

Compare all sorting algorithms interactively. Use the dropdown to switch between algorithms and observe how each one approaches the problem differently:

QuickSort
Time: O(n log n)Space: O(log n)Comparisons: 0Swaps: 0
1 / 0
✓ Use when:General purpose, cache-friendly, average O(n log n) with low constant factor
✗ Avoid when:Already sorted data without randomization, many duplicate keys
Pseudocode
1quickSort(arr, low, high):
2  if (low < high)
3    pivot = partition(arr, low, high)
4    quickSort(arr, low, pivot-1)
5    quickSort(arr, pivot+1, high)
6 
7partition(arr, low, high):
8  pivot = arr[high]
9  i = low - 1
10  for (j = low; j < high; j++)
11    if (arr[j] <= pivot)
12      i++; swap(arr[i], arr[j])
13  swap(arr[i+1], arr[high])
14  return i + 1
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Size20
Default
Default
Comparing
Comparing
Swapping
Swapping
Pivot
Pivot
Sorted
Sorted
P · [ ] · R
Loading visualizer...

🔬 Deep Dive

1. QuickSort: The Speed Champion

QuickSort is often the fastest in practice due to excellent cache locality and low constant factors.

Interactive Visualization: See QuickSort in action - watch how the pivot partitions the array:

QuickSort
Time: O(n log n)Space: O(log n)Comparisons: 0Swaps: 0
1 / 0
✓ Use when:General purpose, cache-friendly, average O(n log n) with low constant factor
✗ Avoid when:Already sorted data without randomization, many duplicate keys
Pseudocode
1quickSort(arr, low, high):
2  if (low < high)
3    pivot = partition(arr, low, high)
4    quickSort(arr, low, pivot-1)
5    quickSort(arr, pivot+1, high)
6 
7partition(arr, low, high):
8  pivot = arr[high]
9  i = low - 1
10  for (j = low; j < high; j++)
11    if (arr[j] <= pivot)
12      i++; swap(arr[i], arr[j])
13  swap(arr[i+1], arr[high])
14  return i + 1
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Size15
Default
Default
Comparing
Comparing
Swapping
Swapping
Pivot
Pivot
Sorted
Sorted
P · [ ] · R
Loading visualizer...

JAVA(61 lines)
Code
Loading syntax highlighter...

3-Way Partitioning (Dutch National Flag):

When there are many duplicates, standard QuickSort degrades. 3-way partitioning handles this:

JAVA(23 lines)
Code
Loading syntax highlighter...

Why QuickSort is fast:

Cache locality: Works on contiguous memory
In-place: No extra array allocation
Few swaps: Only swaps when necessary
Branch prediction: Comparison loop is predictable

2. MergeSort: The Stable Workhorse

MergeSort guarantees O(n log n) and stability, making it ideal for objects.

Interactive Visualization: Watch MergeSort divide and conquer:

MergeSort
Time: O(n log n)Space: O(n)Comparisons: 0Writes: 0
1 / 0
✓ Use when:Stable sort needed, linked lists, external sorting, guaranteed O(n log n)
✗ Avoid when:Memory-constrained environments (needs O(n) extra space)
Pseudocode
1mergeSort(arr, l, r):
2  if (l < r)
3    mid = (l + r) / 2
4    mergeSort(arr, l, mid)
5    mergeSort(arr, mid+1, r)
6    merge(arr, l, mid, r)
7 
8merge(arr, l, mid, r):
9  // merge left and right subarrays
10  while (i < left.len && j < right.len)
11    if (left[i] <= right[j])
12      arr[k++] = left[i++]
13    else arr[k++] = right[j++]
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Size15
Default
Default
Comparing
Comparing
Swapping
Swapping
Pivot
Pivot
Sorted
Sorted
P · [ ] · R
Loading visualizer...

JAVA(70 lines)
Code
Loading syntax highlighter...

Why stability matters:

JAVA(11 lines)
Code
Loading syntax highlighter...

3. HeapSort: The Memory Champion

HeapSort achieves O(n log n) worst case with O(1) extra space.

JAVA(46 lines)
Code
Loading syntax highlighter...

Heap visualization:

TEXT(14 lines)
Code
Loading syntax highlighter...

Why HeapSort isn't the default:

Poor cache locality (jumps around the array)
More comparisons than QuickSort
Not stable
But: guaranteed O(n log n) and O(1) space

4. TimSort: Java's Default

TimSort is a hybrid algorithm combining MergeSort and InsertionSort, optimized for real-world data.

JAVA(31 lines)
Code
Loading syntax highlighter...

What makes TimSort special:

Exploits existing order: Finds natural runs in data
Adaptive: Nearly-sorted data is O(n)
Stable: Critical for object sorting
Galloping mode: Optimizes unbalanced merges

Real TimSort run detection:

JAVA(8 lines)
Code
Loading syntax highlighter...

5. The Comparison Lower Bound: Ω(n log n)

Why can't we sort faster than O(n log n) using comparisons?

Proof using decision trees:

TEXT(17 lines)
Code
Loading syntax highlighter...

This means:

No comparison-based sort can beat O(n log n)
QuickSort, MergeSort, HeapSort are asymptotically optimal
To go faster, we need non-comparison sorts (Part 5)

⚠️ Common Mistakes

Mistake 1: QuickSort with Bad Pivot on Sorted Data

JAVA(18 lines)
Code
Loading syntax highlighter...

Mistake 2: Unstable Sort for Objects

JAVA(14 lines)
Code
Loading syntax highlighter...

Mistake 3: Not Using Insertion Sort for Small Arrays

JAVA(14 lines)
Code
Loading syntax highlighter...

🐛 Debug This

The following QuickSort has a subtle bug. Find it:

JAVA(39 lines)
Code
Loading syntax highlighter...

Click to reveal the bug and solution

The Bug:

The recursive call quickSort(arr, low, pivotIndex) should be quickSort(arr, low, pivotIndex - 1).

With pivotIndex included in the left partition, when pivot ends up at high, we recursively call:

quickSort(arr, low, high) - the same range!

Trace for [2, 1]:

TEXT(5 lines)
Code
Loading syntax highlighter...

The Fix:

JAVA(8 lines)
Code
Loading syntax highlighter...

The pivot is already in its final position after partition, so we exclude it from both recursive calls.

💻 Exercises

Exercise 1: Implement Median-of-Three Pivot ⭐

Implement median-of-three pivot selection for QuickSort:

JAVA(5 lines)
Code
Loading syntax highlighter...

Solution

JAVA(19 lines)
Code
Loading syntax highlighter...

Median-of-three avoids worst case on sorted data while being cheaper than random.

Exercise 2: Count Comparisons ⭐⭐

Modify MergeSort to count the number of comparisons:

JAVA(3 lines)
Code
Loading syntax highlighter...

Solution

JAVA(39 lines)
Code
Loading syntax highlighter...

Exercise 3: In-Place MergeSort ⭐⭐⭐

Implement MergeSort using O(1) extra space (in-place merge):

JAVA(4 lines)
Code
Loading syntax highlighter...

Solution

JAVA(37 lines)
Code
Loading syntax highlighter...

Exercise 4: Iterative QuickSort ⭐⭐⭐

Implement QuickSort without recursion (using explicit stack):

JAVA(3 lines)
Code
Loading syntax highlighter...

Solution

JAVA(38 lines)
Code
Loading syntax highlighter...

By always processing the smaller partition first and pushing the larger, we guarantee O(log n) stack space.

Exercise 5: Detect Natural Runs (TimSort Style) ⭐⭐⭐⭐

Implement run detection like TimSort:

JAVA(6 lines)
Code
Loading syntax highlighter...

Solution

JAVA(41 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Question #1: When would you choose HeapSort over QuickSort?

What interviewers want to hear: Understanding of trade-offs and real constraints.

Strong answer: Choose HeapSort when:

Strict memory constraints: HeapSort uses O(1) extra space vs O(log n) for QuickSort's stack
Worst-case guarantee required: HeapSort is always O(n log n), QuickSort can degrade to O(n²)
Embedded systems: Predictable performance matters more than average speed
Partial sorting: To find top-k elements, build heap in O(n), extract k in O(k log n)

However, QuickSort is usually preferred because:

Better cache locality (sequential access pattern)
Lower constant factors
In practice, O(n²) is avoidable with good pivot selection

Question #2: Explain why MergeSort is stable but QuickSort is not.

What interviewers want to hear: Deep understanding of algorithm mechanics.

Strong answer: Stability definition: Equal elements maintain their relative order.

MergeSort is stable because: During merge, when elements are equal, we always take from the left subarray first:

JAVA(3 lines)
Code
Loading syntax highlighter...

Equal elements from the left half (which came earlier in the original array) are placed first.

QuickSort is unstable because: During partition, elements are swapped based on comparison with pivot. The relative order of equal elements is not preserved:

JAVA(2 lines)
Code
Loading syntax highlighter...

Elements equal to the pivot can end up in either partition depending on their position.

Question #3: Why does Java use different sorting algorithms for primitives vs objects?

What interviewers want to hear: Knowledge of Java internals and practical trade-offs.

Strong answer: Before Java 7:

Primitives: QuickSort (faster, no stability needed)
Objects: MergeSort (stable, needed for Comparable contract)

After Java 7:

Primitives: Dual-Pivot QuickSort (even faster)
Objects: TimSort (stable, adaptive)

Reasons:

Stability requirement: Objects sorted by Comparator should maintain relative order for equals. MergeSort/TimSort guarantee this.
Comparison cost: Object comparison (calling compareTo()) is expensive. TimSort minimizes comparisons through runs.
Primitive comparison is cheap: QuickSort's fewer swaps and better cache performance win for primitives.
Real-world data patterns: TimSort exploits partially sorted data common in objects (timestamps, IDs).

Question #4: How would you sort a nearly-sorted array efficiently?

What interviewers want to hear: Adaptive algorithms knowledge.

Strong answer: For nearly-sorted data:

Best options:

Insertion Sort: O(n) for nearly sorted because elements are close to their final position
TimSort: Detects natural runs, nearly-sorted input is O(n)
Adaptive ShellSort: Exploits partial order

Why these work:

Insertion sort moves elements short distances efficiently
TimSort identifies long runs and minimizes merge work
Already-sorted subsequences are preserved

Avoid:

HeapSort: Always O(n log n), doesn't exploit order
Standard QuickSort: Sorted data can trigger O(n²)

JAVA(6 lines)
Code
Loading syntax highlighter...

Question #5: Prove that any comparison-based sort requires Ω(n log n) comparisons.

What interviewers want to hear: Theoretical understanding with clear reasoning.

Strong answer: Proof outline:

Sorting n distinct elements means determining which of n! permutations is correct
Each comparison answers a yes/no question, eliminating at most half of remaining permutations
A comparison-based sort is a decision tree where:
- Internal nodes are comparisons
- Leaves are permutations (sorted outputs)
- Tree must have at least n! leaves
A binary tree with L leaves has height at least log₂(L)
Therefore: height ≥ log₂(n!)

Using Stirling's approximation:

log₂(n!) ≈ log₂((n/e)^n × √(2πn))
         = n log₂(n) - n log₂(e) + O(log n)
         ≈ n log₂(n)

Conclusion: Any comparison sort needs at least Ω(n log n) comparisons

This is a lower bound - no comparison-based algorithm can beat it. Non-comparison sorts (counting, radix) bypass this by not using comparisons.

📋 Quick Reference

Algorithm Selection Guide

TEXT(22 lines)
Code
Loading syntax highlighter...

Complexity Summary

Sort	Best	Average	Worst	Space	Stable
QuickSort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
MergeSort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
HeapSort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
TimSort	O(n)	O(n log n)	O(n log n)	O(n)	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes

Java Sorting Methods

JAVA(13 lines)
Code
Loading syntax highlighter...

📝 Summary & Key Takeaways

Core Principles

QuickSort is fastest on average but has O(n²) worst case - use random pivot
MergeSort guarantees O(n log n) and stability - essential for objects
HeapSort uses O(1) space but has poor cache locality
TimSort adapts to data patterns - Java's smart default choice
Ω(n log n) is the lower bound for comparison-based sorting

What You Can Do Now

Implement all four algorithms from scratch
Choose the right algorithm based on requirements
Explain why Java uses different sorts for primitives vs objects
Prove the comparison sort lower bound
Optimize QuickSort with pivot strategies and 3-way partitioning

📅 Review Schedule

Day	Task	Time
Day 1	Review complexity table	5 min
Day 3	Implement QuickSort with random pivot	15 min
Day 7	Implement HeapSort from memory	15 min
Day 14	Redo Debug This exercise	10 min
Day 30	Explain all four algorithms aloud	15 min

Next in series: [Part 5: Linear Time Sorting - Counting Sort, Radix Sort & Bucket Sort]

📋 At a Glance

🎯 What You'll Learn

🔥 Production Story: The Sorted Data Disaster

🧠 Mental Model: The Sorting Spectrum

🎮 Try It Yourself

QuickSort

🔬 Deep Dive

1. QuickSort: The Speed Champion

QuickSort

2. MergeSort: The Stable Workhorse

MergeSort

3. HeapSort: The Memory Champion

4. TimSort: Java's Default

5. The Comparison Lower Bound: Ω(n log n)

⚠️ Common Mistakes

Mistake 1: QuickSort with Bad Pivot on Sorted Data

Mistake 2: Unstable Sort for Objects

Mistake 3: Not Using Insertion Sort for Small Arrays

🐛 Debug This

💻 Exercises

Exercise 1: Implement Median-of-Three Pivot ⭐

Exercise 2: Count Comparisons ⭐⭐

Exercise 3: In-Place MergeSort ⭐⭐⭐

Exercise 4: Iterative QuickSort ⭐⭐⭐

Exercise 5: Detect Natural Runs (TimSort Style) ⭐⭐⭐⭐

🎤 Interview Questions

Question #1: When would you choose HeapSort over QuickSort?

Question #2: Explain why MergeSort is stable but QuickSort is not.

Question #3: Why does Java use different sorting algorithms for primitives vs objects?

Question #4: How would you sort a nearly-sorted array efficiently?

Question #5: Prove that any comparison-based sort requires Ω(n log n) comparisons.

📋 Quick Reference

Algorithm Selection Guide

Complexity Summary

Java Sorting Methods

📝 Summary & Key Takeaways

Core Principles

What You Can Do Now

📅 Review Schedule

Tags:

QuickSort

QuickSort

MergeSort