Merge Sort

Mergesort

Two classic sorting algorithms: mergesort and quicksort.
- Critical components in the world’s computational infrastructure.
- Full scientific understanding of their properties has enabled development into practical system sorts.
- Quicksort honored as one of top 10 algorithms of 20th century in science and engineering.
Mergesort.
Quicksort.

Mergesort Topics

mergesort
bottom-up mergesort
Sorting complexity
divide-and-conquer

Mergesort

Basic plan:
- Divide array into two halves.
- Recursively sort each half.
- Merge two halves.

Abstract In-Place Merge

Goal: Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi], replace with sorted subarray a[lo] to a[hi].

Merging: Java Implementation

Java implementation of the merge function:

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];int i = lo, j = mid+1;
for (int k = lo; k &lt;= hi; k++) {
    if (i &gt; mid) a[k] = aux[j++];
    else if (j &gt; hi) a[k] = aux[i++];
    else if (less(aux[j], aux[i])) a[k] = aux[j++];
    else a[k] = aux[i++];
}
}

Mergesort Quiz 1

Question: How many calls does merge() make to less() in order to merge two sorted subarrays, each of length $n/2$ , into a sorted array of length $n$ ?
- Options:
  - A. ~ ¼ n to ~ ½ n
  - B. ~ ½ n
  - C. ~ ½ n to ~ n
  - D. ~ n
Best-case input (n/2 compares): A B C D E F G H
Worst-case input (n - 1 compares): A B C H D E F G

Mergesort: Java Implementation

Java implementation of the Merge class:

public class Merge {
    private static void merge(...) { /* as before */ }private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi &lt;= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length - 1);
}
}

Mergesort: Trace

Illustrates the execution of mergesort on an example array, showing the recursive calls and merge operations.

Mergesort Quiz 2

Question: Which of the following subarray lengths will occur when running mergesort on an array of length 12?
- Options:
  - A. { 1, 2, 3, 4, 6, 8, 12 }
  - B. { 1, 2, 3, 6, 12 }
  - C. { 1, 2, 4, 8, 12 }
  - D. { 1, 3, 6, 9, 12 }

Mergesort: Animation

Visualizations of mergesort with 50 random items and 50 reverse-sorted items.

Mergesort: Empirical Analysis

Running time estimates:
- Laptop executes $10^8$ compares/second.
- Supercomputer executes $10^{12}$ compares/second.
Bottom line: Good algorithms are better than supercomputers.
Comparison of insertion sort ( $n^2$ ) and mergesort ( $n \log n$ ) performance on different computers for varying input sizes.

Mergesort Analysis: Number of Compares

Proposition: Mergesort uses $\le n \lg n$ compares to sort an array of length $n$ .
Proof sketch:
- The number of compares $C(n)$ to mergesort an array of length $n$ satisfies the recurrence: $C(n) \le C(\lceil n/2 \rceil) + C(\lfloor n/2 \rfloor) + n – 1$ for n > 1, with $C(1) = 0$ .
- We solve this simpler recurrence, and assume $n$ is a power of 2: $D(n) = 2 D(n / 2) + n$ , for n > 1, with $D(1) = 0$ .

Divide-and-Conquer Recurrence

Proposition: If $D(n)$ satisfies $D(n) = 2 D(n / 2) + n$ for n > 1, with $D(1) = 0$ , then $D(n) = n \lg n$ .
Proof by picture (assuming $n$ is a power of 2).

Mergesort Analysis: Number of Array Accesses

Proposition: Mergesort uses $\le 6 n \lg n$ array accesses to sort an array of length $n$ .
Proof sketch: The number of array accesses $A(n)$ satisfies the recurrence: $A(n) \le A(\lceil n/2 \rceil) + A(\lfloor n/2 \rfloor) + 6 n$ for n > 1, with $A(1) = 0$ .

Key point: Any algorithm with the following structure takes $n \log n$ time:

public static void f(int n) {
    if (n == 0) return;
    f(n/2);
    f(n/2);
    linear(n);
}

Notable examples: FFT, hidden-line removal, Kendall-tau distance, …

Mergesort Analysis: Memory

Proposition: Mergesort uses extra space proportional to $n$ .
Proof: The array aux[] needs to be of length $n$ for the last merge.
Definition: A sorting algorithm is in-place if it uses $\le c \log n$ extra memory.
Examples: Insertion sort and selection sort.
Challenge 1 (not hard): Use aux[] array of length ~ ½ $n$ instead of $n$ .
Challenge 2 (very hard): In-place merge. [Kronrod 1969]

Mergesort Quiz 3

Question: Is our implementation of mergesort stable?
- Options:
  - A. Yes.
  - B. No, but it can be easily modified to be stable.
  - C. No, mergesort is inherently unstable.
  - D. I don’t remember what stability means.
Definition: A sorting algorithm is stable if it preserves the relative order of equal keys.

Stability: Mergesort

Proposition: Mergesort is stable.
Proof: Suffices to verify that merge operation is stable.

Stability: Mergesort

Proposition: Merge operation is stable.
Proof: Takes from left subarray if equal keys.

Mergesort: Practical Improvements

Use insertion sort for small subarrays.

Mergesort has too much overhead for tiny subarrays.
Cutoff to insertion sort for » 10 items.

private static void sort(...) {
    if (hi <= lo + CUTOFF - 1) {
        Insertion.sort(a, lo, hi);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort (a, aux, lo, mid);
    sort (a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}

Mergesort with Cutoff to Insertion Sort: Visualization

Visualization of mergesort with a cutoff to insertion sort, showing the first subarray, second subarray, first merge, first half sorted, second half sorted, and the result.

Mergesort: Practical Improvements

Stop if already sorted.

Is largest item in first half ≤ smallest item in second half?
Helps for partially ordered arrays.

private static void sort(...) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort (a, aux, lo, mid);
    sort (a, aux, mid+1, hi);
    if (!less(a[mid+1], a[mid])) return;
    merge(a, aux, lo, mid, hi);
}

Mergesort: Practical Improvements

Eliminate the copy to the auxiliary array.

Save time (but not space) by switching the role of the input and auxiliary array in each recursive call.

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) aux[k] = a[j++];
        else if (j > hi) aux[k] = a[i++];
        else if (less(a[j], a[i])) aux[k] = a[j++];
        else aux[k] = a[i++];
    }
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort (aux, a, lo, mid);
    sort (aux, a, mid+1, hi);
    merge(a, aux, lo, mid, hi); // merge from a[] to aux[]
}

Assumes aux[] is initialized to a[] once, before recursive calls. Switch roles of aux[] and a[].

Java 6 System Sort

Basic algorithm in Arrays.sort() for sorting objects = mergesort.
- Cutoff to insertion sort = 7.
- Stop-if-already-sorted test.
- Eliminate-the-copy-to-the-auxiliary-array trick.

Bottom-Up Mergesort

mergesort
bottom-up mergesort
sorting complexity
divide-and-conquer

Bottom-Up Mergesort

Basic plan:
- Pass through array, merging subarrays of size 1.
- Repeat for subarrays of size 2, 4, 8, ….

Bottom-Up Mergesort: Java Implementation

Java implementation of bottom-up mergesort:

public class MergeBU {
    private static void merge(...) { /* as before */ }public static void sort(Comparable[] a) {
    int n = a.length;
    Comparable[] aux = new Comparable[n];
    for (int sz = 1; sz &lt; n; sz = sz+sz)
        for (int lo = 0; lo &lt; n-sz; lo += sz+sz)
            merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1));
}
}

Mergesort: Visualizations

Visualizations of top-down and bottom-up mergesort (cutoff = 12).

Mergesort Quiz 4

Question: Which is faster in practice: top-down mergesort or bottom-up mergesort? You may assume $n$ is a power of 2.
- Options:
  - A. Top-down (recursive) mergesort.
  - B. Bottom-up (non-recursive) mergesort.
  - C. No observable difference.
  - D. I don't know.

Natural Mergesort

Idea: Exploit pre-existing order by identifying naturally occurring runs.
Tradeoff: Fewer passes vs. extra compares per pass to identify runs.

Timsort

Natural mergesort.
Use binary insertion sort to make initial runs (if needed).
A few more clever optimizations.
Consequence: Linear time on many arrays with pre-existing order.
Now widely used: Python, Java 7–9, GNU Octave, Android, ….

Sorting Summary

	in-place?	stable?	best	average	worst	remarks
selection	✔			½ $n^2$	½ $n^2$	$n$ exchanges
insertion	✔	✔	$n$	¼ $n^2$	½ $n^2$	use for small $n$ or partially ordered
shell	✔		$n \log_3 n$	?	$c n^{3/2}$	tight code; subquadratic
merge		✔	½ $n \lg n$	$n \lg n$	$n \lg n$	$n \log n$ guarantee; stable
timsort		✔	$n$			improves mergesort when pre-existing order
?	✔	✔	$n$	$n \lg n$	$n \lg n$	holy sorting grail

Sorting Complexity

mergesort
bottom-up mergesort
Sorting complexity
divide-and-conquer

Complexity of Sorting

Computational complexity: Framework to study efficiency of algorithms for solving a particular problem $X$ .
Model of computation: Allowable operations.
Cost model: Operation counts.
Upper bound: Cost guarantee provided by some algorithm for $X$ .
Lower bound: Proven limit on cost guarantee of all algorithms for $X$ .
Optimal algorithm: Algorithm with best possible cost guarantee for $X$ . lower bound ~ upper bound
Complexity of sorting
- model of computation: decision tree
- cost model: # compares
- upper bound: ~ $n \lg n$ from mergesort
- lower bound: ?
- optimal algorithm: ?
- can access information only through compares (e.g., Java Comparable framework)

Decision Tree

Decision tree for 3 distinct keys a, b, and c. Each leaf corresponds to one ordering.

Compare-Based Lower Bound for Sorting

Proposition: Any compare-based sorting algorithm must make at least $\lg (n !) ~ n \lg n$ compares in the worst-case.
Proof:
- Assume array consists of $n$ distinct values $a<em>1$ through $a</em>n$ .
- Worst case dictated by height $h$ of decision tree.
- Binary tree of height $h$ has at most $2^h$ leaves.
- $n!$ different orderings ⇒ at least $n!$ leaves.

Compare-Based Lower Bound for Sorting

Proposition: Any compare-based sorting algorithm must make at least $\lg (n !) ~ n \lg n$ compares in the worst-case.
Proof:
- Assume array consists of $n$ distinct values $a<em>1$ through $a</em>n$ .
- Worst case dictated by height $h$ of decision tree.
- Binary tree of height $h$ has at most $2^h$ leaves.
- $n!$ different orderings ⇒ at least $n!$ leaves.
2^h \ge # leaves \ge n! \implies h \ge \lg(n!)
- Stirling’s formula ~ $n \lg n$

Complexity of Sorting

Model of computation: decision tree
Cost model: # compares
Upper bound: ~ $n \lg n$
Lower bound: ~ $n \lg n$
Optimal algorithm: mergesort

Complexity Results in Context

Compares? Mergesort is optimal with respect to number compares.
Space? Mergesort is not optimal with respect to space usage.
Lessons:
- Use theory as a guide.
- Ex. Design sorting algorithm that guarantees ~ ½ $n \lg n$ compares?
- Ex. Design sorting algorithm that is both time- and space-optimal?

Complexity Results in Context

Lower bound may not hold if the algorithm can take advantage of:
- The initial order of the input array.
  - Ex: insertion sort requires only a linear number of compares on partially sorted arrays.
- The distribution of key values.
  - Ex: 3-way quicksort requires only a linear number of compares on arrays with a constant number of distinct keys.
- The representation of the keys.
  - Ex: radix sorts require no key compares — they access the data via character/digit compares.

Commonly Used Notations in the Theory of Algorithms

Notation	Provides	Example	Shorthand for
Tilde	leading term	~ ½ $n^2$	½ $n^2$
Big Theta	order of growth	Θ( $n^2$ )	½ $n^2$ , 10 $n^2$ , 5 $n^2$ + 22 $n \log n$ + 3 $n$
Big O	upper bound	O( $n^2$ )	10 $n^2$ , 100 $n^2$ , 22 $n \log n$ + 3 $n$
Big Omega	lower bound	Ω( $n^2$ )	½ $n^2$ , $n^5$ , 5 $n^3$ + 22 $n \log n$ + 3 $n$

Sorting Complexity

mergesort
bottom-up mergesort
Sorting complexity
divide-and-conquer

Sorting a Linked List

Problem: Given a singly linked list, rearrange its nodes in sorter order.
Version 1: Linearithmic time, linear extra space.
Version 2: Linearithmic time, logarithmic (or constant) extra space.