🎯 Mergesort

A Comprehensive Study Guide

📚 Table of Contents

📖 Overview

What is Mergesort?

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.

🎯 Basic Plan

  1. Divide: Split the array into two halves
  2. Conquer: Recursively sort each half
  3. Combine: Merge the two sorted halves together

Example: Sorting "MERGESORTEXAMPLE"

Input:

M E R G E S O R T E X A M P L E

⬇️ After sorting left half ⬇️

E E G M O R R S T E X A M P L E

⬇️ After sorting right half ⬇️

E E G M O R R S A E E L M P T X

⬇️ After merging ⬇️

A E E E E G L M M O P R R S T X

⚙️ How Mergesort Works

The Merge Operation

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].

Merge Example

Two sorted subarrays:

E E G M R | A C E R T

⬇️ After merging ⬇️

A C E E E G M R R T

Merge Algorithm Steps

  1. Copy both subarrays to an auxiliary array
  2. Compare elements from each subarray
  3. Select the smaller element and place it in the result
  4. Repeat until all elements are merged

💻 Java Implementation

Merge Method

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
    }
}

Top-Down Mergesort

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);
    }
}

📝 Key Implementation Notes

  • The auxiliary array is created once and reused throughout recursion
  • The merge operation is in-place (modifies original array)
  • The algorithm is not truly in-place (requires O(N) extra space)
  • Base case: when subarray has 1 or 0 elements, it's already sorted

📊 Complexity Analysis

Time Complexity

O(N log N)

Best, Average, and Worst Case

Space Complexity

O(N)

For auxiliary array

Compares

≤ N lg N

Upper bound

Array Accesses

≤ 6N lg N

Upper bound

Why O(N log N)?

Recurrence Relation:

T(N) = 2T(N/2) + N

  • 2T(N/2): Two recursive calls on halves of the array
  • N: Linear time to merge the two halves
  • Depth of recursion tree: log₂ N (divide by 2 each time)
  • Work at each level: N (merge operations)
  • Total work: N × log₂ N = O(N log N)

Empirical Analysis

Computer Thousand (10³) Million (10⁶) Billion (10⁹)
Home (10⁸ compares/sec) instant 1 second 18 minutes
Super (10¹² compares/sec) instant instant instant

✨ Bottom Line

Good algorithms are better than supercomputers!

Mergesort on a home computer beats Insertion Sort (O(N²)) on a supercomputer for large datasets.

🔄 Bottom-Up Mergesort

Alternative Approach: Non-Recursive

Instead of recursively dividing the array, start with small subarrays and iteratively merge them.

Algorithm

  1. Pass through array, merging subarrays of size 1
  2. Repeat for subarrays of size 2, 4, 8, 16, ...
  3. Continue until entire array is sorted

Implementation

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));
        }
    }
}

✅ Advantages

  • Simple and elegant
  • No recursion overhead
  • Same O(N log N) guarantee
  • Good for systems without recursion support

❌ Disadvantages

  • About 10% slower than top-down on typical systems
  • Less cache-friendly
  • Harder to optimize with cutoff to insertion sort

⚖️ Stability

What is Stability?

A sorting algorithm is stable if it preserves the relative order of items with equal keys.

Why Does Stability Matter?

Typical Use Case: Sort by multiple criteria

  1. First, sort by name (alphabetically)
  2. Then, sort by section number

With a stable sort, students in the same section remain sorted by name!

Example: Student Records

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!

Is Mergesort Stable?

✅ Yes! Mergesort is Stable

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

Stability Comparison

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

🔧 Comparators

What is a Comparator?

A Comparator is a Java interface that allows you to define custom comparison logic, separate from the natural ordering of a type.

Comparable vs Comparator

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)

Example: Student Comparators

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());

Common String Orderings

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

📝 Summary & Comparison

Sorting Algorithm Comparison

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

✅ Mergesort Advantages

  • Guaranteed O(N log N) in all cases
  • Stable - preserves relative order
  • Predictable performance
  • Parallelizable
  • Good for external sorting
  • Used in Java's Arrays.sort() for objects

❌ Mergesort Disadvantages

  • Not in-place - requires O(N) extra space
  • Slower than quicksort in practice
  • Not adaptive to pre-sorted data
  • Overhead from array copying

🎯 When to Use Mergesort

  • Stability is required (sorting by multiple keys)
  • Guaranteed O(N log N) is essential
  • Working with linked lists (can be in-place with lists)
  • External sorting (data doesn't fit in memory)
  • Parallel sorting (easy to parallelize)
  • Extra space is not a concern

🔑 Key Takeaways

  1. Mergesort achieves O(N log N) through divide-and-conquer
  2. The merge operation is the key to the algorithm
  3. It's stable and has guaranteed performance
  4. Trade-off: O(N) space for O(N log N) time
  5. Bottom-up version eliminates recursion overhead
  6. Used extensively in practice (Java, Python, etc.)

🎓 Study Tips

  • ✏️ Practice tracing the algorithm on paper with small examples
  • 💡 Understand the recurrence: T(N) = 2T(N/2) + N
  • 🔍 Focus on the merge operation - it's the heart of the algorithm
  • 📊 Compare with other sorts - know the trade-offs
  • 💻 Implement both versions - top-down and bottom-up
  • 🎯 Remember stability - key advantage over quicksort
  • 📝 Practice complexity analysis - time and space