A Comprehensive Study Guide
Mergesort is a classic divide-and-conquer sorting algorithm that was one of the first algorithms to achieve O(N log N) time complexity. It's considered one of the top 10 algorithms of the 20th century in science and engineering.
Input:
M E R G E S O R T E X A M P L Eβ¬οΈ After sorting left half β¬οΈ
β¬οΈ After sorting right half β¬οΈ
β¬οΈ After merging β¬οΈ
Goal: Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi], replace with a single sorted subarray a[lo] to a[hi].
Two sorted subarrays:
β¬οΈ After merging β¬οΈ
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// Copy elements to auxiliary array
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
// Merge back to original array
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++]; // left exhausted
else if (j > hi) a[k] = aux[i++]; // right exhausted
else if (less(aux[j], aux[i])) a[k] = aux[j++]; // right smaller
else a[k] = aux[i++]; // left smaller or equal
}
}public class Merge {
private static void merge(...) { /* as above */ }
private static void sort(Comparable[] a, Comparable[] aux,
int lo, int hi) {
if (hi <= lo) return; // base case
int mid = lo + (hi - lo) / 2; // find midpoint
sort(a, aux, lo, mid); // sort left half
sort(a, aux, mid + 1, hi); // sort right half
merge(a, aux, lo, mid, hi); // merge results
}
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
}Best, Average, and Worst Case
For auxiliary array
Upper bound
Upper bound
Recurrence Relation:
T(N) = 2T(N/2) + N
| Computer | Thousand (10Β³) | Million (10βΆ) | Billion (10βΉ) |
|---|---|---|---|
| Home (10βΈ compares/sec) | instant | 1 second | 18 minutes |
| Super (10ΒΉΒ² compares/sec) | instant | instant | instant |
Good algorithms are better than supercomputers!
Mergesort on a home computer beats Insertion Sort (O(NΒ²)) on a supercomputer for large datasets.
Instead of recursively dividing the array, start with small subarrays and iteratively merge them.
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
// sz: size of subarrays to merge (1, 2, 4, 8, ...)
for (int sz = 1; sz < N; sz = sz + sz) {
// lo: start of left subarray
for (int lo = 0; lo < N - sz; lo += sz + sz) {
merge(a, aux, lo, lo + sz - 1,
Math.min(lo + sz + sz - 1, N - 1));
}
}
}A sorting algorithm is stable if it preserves the relative order of items with equal keys.
Typical Use Case: Sort by multiple criteria
With a stable sort, students in the same section remain sorted by name!
| Name | Section | After Sorting by Section (Stable) |
|---|---|---|
| Andrews | 3 | Andrews (3) β Still in order! |
| Chen | 3 | Chen (3) β Still in order! |
| Fox | 3 | Fox (3) β Still in order! |
Key insight: The merge operation takes from the left subarray when keys are equal.
if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++]; // Takes from left if equal| Algorithm | Stable? | Reason |
|---|---|---|
| Insertion Sort | β Yes | Equal items never move past each other |
| Selection Sort | β No | Long-distance exchanges can move equal items |
| Mergesort | β Yes | Merge operation preserves order |
| Shell Sort | β No | Long-distance exchanges |
A Comparator is a Java interface that allows you to define custom comparison logic, separate from the natural ordering of a type.
| Comparable | Comparator |
|---|---|
| Natural order (part of class) | Alternative order (separate class) |
compareTo() method |
compare() method |
| One ordering per class | Multiple orderings possible |
Arrays.sort(array) |
Arrays.sort(array, comparator) |
public class Student {
private final String name;
private final int section;
// Comparator for sorting by name
public static class ByName implements Comparator<Student> {
public int compare(Student v, Student w) {
return v.name.compareTo(w.name);
}
}
// Comparator for sorting by section
public static class BySection implements Comparator<Student> {
public int compare(Student v, Student w) {
return v.section - w.section;
}
}
}
// Usage:
Arrays.sort(students, new Student.ByName());
Arrays.sort(students, new Student.BySection());| Order Type | Example |
|---|---|
| Natural | Now is the time |
| Case Insensitive | is Now the time |
| Spanish | cafΓ© cafetero churro cuarto nube Γ±oΓ±o |
| British Phone Book | McKinley Mackintosh |
| Algorithm | In-Place? | Stable? | Best | Average | Worst | Remarks |
|---|---|---|---|---|---|---|
| Selection Sort | β | β | Β½NΒ² | Β½NΒ² | Β½NΒ² | N exchanges |
| Insertion Sort | β | β | N | ΒΌNΒ² | Β½NΒ² | Use for small N or partially ordered |
| Shell Sort | β | β | N log N | ? | N^(3/2) | Tight code; subquadratic |
| Mergesort | β | β | Β½N log N | N log N | N log N | N log N guarantee; stable |
Arrays.sort() for objectsQ: Write the recurrence relation for mergesort's time complexity and solve it to show the result is O(N log N).
A: The recurrence is T(N) = 2T(N/2) + N, where 2T(N/2) accounts for recursively sorting two halves and N for merging them. By the Master Theorem (Case 2: a=2, b=2, f(N)=N, N^log_b(a) = N^1 = N), T(N) = Ξ(N log N). Alternatively, using the recursion tree: there are logβ N levels, and each level does exactly N total work (merging all subarrays at that level sums to N). Total work = N Γ logβ N = O(N log N).
Q: Trace the merge of the two sorted subarrays [1, 3, 5, 7] and [2, 4, 6, 8] step by step. How many comparisons are made in the worst case?
A: i=0 (points to [1,3,5,7]), j=0 (points to [2,4,6,8]).
Compare 1 vs 2 β take 1. Compare 2 vs 3 β take 2. Compare 3 vs 4 β take 3. Compare 4 vs 5 β take 4. Compare 5 vs 6 β take 5. Compare 6 vs 7 β take 6. Compare 7 vs 8 β take 7. Left exhausted β take 8.
Result: [1, 2, 3, 4, 5, 6, 7, 8]. Total comparisons: 7 = N-1, where N=8. The worst case for merging two halves of size N is N-1 comparisons (perfectly interleaved). Best case is N/2 comparisons (one half is entirely smaller).
Q: Explain precisely why mergesort is stable, referring to the specific line of code that ensures stability.
A: Mergesort is stable because the merge operation takes elements from the LEFT subarray when the two elements being compared are equal. In the merge code: else a[k] = aux[i++]; β this branch executes when aux[j] is NOT strictly less than aux[i], i.e., when they are equal or the left element is smaller. By always choosing the left element when values are equal, the original relative order of equal elements is preserved across the merge. Since all recursive calls ultimately build on this stable merge, the entire sort is stable. In contrast, if the code used less(aux[i], aux[j]) and took from the right on equality, stability would be broken.
Q: Compare top-down (recursive) and bottom-up (iterative) mergesort. When might you prefer bottom-up?
A: Both algorithms have identical O(N log N) time complexity and O(N) space, and both are stable. The key differences:
- Top-down uses recursion (call stack overhead, ~log N frames), cleaner conceptually, easier to add optimizations like a cutoff to insertion sort for small subarrays.
- Bottom-up is iterative (no recursion), starting with subarrays of size 1 and doubling. It has no function call overhead, which makes it about 10% faster on some systems. It is also preferable in languages/environments that restrict recursion depth, and works naturally for sorting linked lists without requiring random access. Bottom-up is the approach used in Java's Arrays.sort() for primitive types in some implementations.
Q: Why does mergesort require O(N) extra space? Can mergesort be made truly in-place (O(1) extra space)?
A: The merge operation requires an auxiliary array because merging two sorted halves in-place without extra space is extremely complex and slow β any simple in-place merge degrades to O(NΒ²) due to element shifting. The standard merge copies both halves to an auxiliary array and merges back, requiring exactly N extra cells.
Theoretically, O(1)-space mergesort exists but is impractical: it requires complex block-merge algorithms with O(N log N) time but very large constants. In practice, mergesort always uses O(N) auxiliary space, which is why quicksort (O(log N) stack space) is preferred when memory is constrained.
Q: What is the difference between Comparable and Comparator in Java? Give a scenario where a Comparator is necessary.
A: Comparable<T> is implemented by a class to define its natural ordering via compareTo(). A class can have only one natural ordering. Comparator<T> is a separate object that defines an alternative ordering via compare(a, b). A class can have many comparators.
Scenario: A Student class has a natural ordering by student ID. You need to sort a list of students first by GPA (descending) then by name (alphabetical) as a tiebreaker. You cannot redefine the natural order, so you create a custom Comparator<Student> and pass it to Arrays.sort(students, comparator). Mergesort uses the comparator's compare() instead of compareTo().
Q: Name three concrete differences between mergesort and quicksort, and explain when you would choose mergesort.
A:
1. Stability: Mergesort is stable; standard quicksort is not. Choose mergesort when you need to sort by multiple keys in sequence (sort by name, then re-sort by grade β mergesort preserves the name order within each grade).
2. Worst-case guarantee: Mergesort is always O(N log N); quicksort degrades to O(NΒ²) on sorted or nearly sorted input (without shuffling). Choose mergesort for real-time systems where worst-case latency matters.
3. Space: Mergesort needs O(N) extra space; quicksort needs only O(log N) stack space. Choose quicksort when memory is tight.
Java uses mergesort (TimSort) for object arrays (stability required) and a dual-pivot quicksort for primitive arrays (stability not needed, speed prioritized).
Q: A classmate says "Mergesort is O(N log N) on average but O(NΒ²) in the worst case, just like quicksort." Are they correct?
A: The classmate is wrong. Mergesort is O(N log N) in the best, average, AND worst case. The recurrence T(N) = 2T(N/2) + N holds for ALL inputs because the split is always at the midpoint β there is no "bad pivot" analog. The best case is slightly better: Β½N log N comparisons (when the two halves are already in perfect interleaved order, saving comparisons during merge). But the worst case remains N log N, not NΒ². This guaranteed O(N log N) worst case is mergesort's key advantage over quicksort.