COS 226 Lecture 4: Mergesort Merging two sorted files
Prototypical divide-and-conquer algorithm #define T Item
merge(T c[], T a[], int N, T b[], int M )
{ int i, j, k;
for (i = 0, j = 0, k = 0; k < N+M; k++)
{
if (i == N) { c[k] = b[j++]; continue; }
if (j == M) { c[k] = a[i++]; continue; }
if (less(a[i], b[j]))
c[k] = a[i++]; else c[k] = b[j++];
}
}
4.1 4.3
Why study mergesort? Merging example
Guaranteed to run in O(N log N) steps
Method of choice for linked lists
A R S T G I N
A R S T G I N
Drawback:
R S T G I N A
Linear extra space R S T I N A G
(can only sort half the memory) R S T N A G I
R S T A G I N
An "optimal" sorting method S T A G I N R
T A G I N R S
A G I N R S T
Leads us to consider
recurrence relationships
computational complexity Trivial computation?
deep hacking
fractals Try doing it without using linear extra space
4.2 4.4
Abstract inplace merge Mergesort example
Easier for calling routine to assume merge is inplace
assume files to be merged are both in arg array
copy files into temp array A S O R T I N G E X A M P L E
A S
merge back into arg array O R
A O R S
Trick: reverse second file when copying I T
avoids special tests for ends of arrays G N
G I N T
A G I N O R S T
E X
A R S T G I N
A M
A R S T N I G
A E M X
R S T N I G A
L P
R S T N I A G
E L P
R S T N A G I
A E E L M P X
R S T A G I N
A A E E G I L M N O P R S T X
S T A G I N R
T A G I N R S
A G I N R S T 4.5 4.7
Abstract inplace merge implementation Mergesort implementation
void mergesort(Item a[], int l, int r)
Item aux[maxN]; {
merge(Item a[], int l, int m, int r) int m = (r+l)/2;
{ int i, j, k; if (r <= l) return;
for (i = m+1; i > l; i--) aux[i-1] = a[i-1]; mergesort(a, l, m);
for (j = m; j < r; j++) aux[r+m-j] = a[j+1]; mergesort(a, m+1, r);
for (k = l; k <= r; k++) merge(a, l, m, r);
if (less(aux[i], aux[j])) }
a[k] = aux[i++]; else a[k] = aux[j--];
} Tree structures describe merge file sizes
16 21
8 8 10 11
4 4 4 4 5 5 5 6
2 2 2 2 2 2 2 2 2 3 2 3 2 3 3 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 2 1 2 1 2
1 1 1 1 1 1 1 1 1 1
4.6 4.8
Recurrences Mergesort and numbers
Direct relationship to recursive programs THM: Number of compares used by Mergesort for
(most programs are "recursive") is the same as
number of bits in the binary representations
Easy telescoping recurrences of all the numbers less than N (plus N-1).
T(N) = T(N-1) + 1 T(N) = N
T(2^n) = T(2^(n-1)) + 1 T(N) = lg N if N=2^n Proof: They satisfy the same recurrence
C(2N) = C(N) + C(N) + 2N
Short list of important recurrences C(2N+1) = C(N) + C(N+1) + 2N+1
T(N) = T(N/2) + 1 T(N) = lg N
T(N) = T(N/2) + N T(N) = N 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
T(N) = 2T(N/2) + 1 T(N) = N 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0
T(N) = 2T(N/2) + N T(N) = N lg N 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1
Details in Chapter 2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
4.9 4.11
Mergesort analysis Mergesort and fractals
THM: Mergesort uses N lg N comparisons Divide-and-conquer algs exhibit erratic periodic behavior
Proof: number of bits in numbers less than N
From code, = number of 0 bits + number of 1 bits
T(N) = 2T(N/2) + N = (N lg N)/2 + periodic term
For N = 2^n (n = lg N), + (N lg N)/2 + periodic term
T(2^n) = 2T(2^(n-1)) + 2^n = N lg N + periodic term
Divide both sides by 2^n
T(2^n)/2^n = T(2^(n-1))/2^(n-1) + 1
Telescope: 108
T(2^n)/2^n = n
Therefore, 54
T(N) = N lg N
27
0
-18
-36
Exact for powers of two, approximate otherwise
-72
32 64 128 256 512
4.10 4.12
Guaranteed worst-case bound
Divide-and-conquer Complexity of sorting
Basic algorithm design paradigm N lg N comparisons necessary and sufficient
"Master Theorem" for analyzing algorithms Upper bound: N lg N (Mergesort)
T(N) = aT(N/b) + N^c(lg N)^d Lower bound: N lg N - N/(ln 2) + lg N
Interested in learning more? THM: All comparison-based sorting methods
Stay tuned for a few more in CS 226 must use at least N lg N comparisons
Take CS 341, CS 423 Proof:
Read "Introduction to the Analysis of Algs" COMPARISON TREE (all sequences of comparisons)
by Sedgewick and Flajolet
4.13 4.15
Computational Complexity Comparison tree for sorting
Framework to study efficiency of algorithms 1<2?
1<3? 1<4?
Machine model: count fundamental operations
2<3? 3<4?
Average case: 1<3?
predict performance (need input model)
Worst case:
guarantee performance (any input) Path from root to leaf describes operation
of sorting algorithm on given input
Upper bound: algorithm to solve the problem
Lower bound: proof that no algorithm can do Claim 1: at least N! leaves
Claim 2: height at least lg N!
Complexity studies provide Claim 3: (Stirling’s formula for lg N!)
starting point for practical implementations height at least N lg N - N/(ln 2) + lg N
indication of approaches to be avoided
Caveat: what if we don’t use comparisons??
4.14 4.16
Stay tuned for radix sort
Mergesort without move Bottom-up mergesort
Alternative to abstract inplace merge Pass through the file
merge adjacent subfiles
void mergesort(T a[], T b[], int l, int r) size doubles each time through
{ int m = (l+r)/2;
A S O R T I N G E X A M P L E
if (r-l <= 10)
A S
{ insertion(a, l, r); return; }
O R
mergesort(b, a, l, m); I T
mergesort(b, a, m+1, r); G N
merge(a+l, b+l, m-l+1, b+m+1, r-m); E X
} A M
L P
void sort(Item a[], int l, int r)
A O R S
{ int i; G I N T
for (i = l; i <= r; i++) aux[i] = a[i]; A E M X
mergesort(a, aux, l, r); E L P
} A G I N O R S T
A E E L M P X
4.17 A A E E G I L M N O P R S T X 4.19
Deep hacking on Mergesort inner loop Bottom-up mergesort implementation
CODE OPTIMIZATION: Improve performance by tuning code void mergesort(Item a[], int l, int r)
concentrate on inner loop { int i, m;
for (m = 1; m < r-l; m = m+m)
For mergesort, for (i = l; i <= r-m; i += m+m)
Avoid move with recursive argument switch merge(a, i, i+m-1, min(i+m+m-1, r));
Avoid sentinels with "up-down" trick }
Combine the two? Doable, but mindbending Different set of merges than for top-down
unless N is a power of two
Can make mergesort almost as fast as quicksort
mergesort inner loop: compare, store, two incs
quicksort inner loop: compare, inc 21
16 5
8 8 5
4 4 4 4 4 1
2 2 2 2 2 2 2 2 2 2 1
4.18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4.20
Merging linked lists Bottom-up list mergesort
Problem: sort data on a linked list Cycle through a circular list
(rearrange list so items are in order)
typedef struct node *link; link mergesort(link t)
struct node { Item item; link next; }; { link u;
for (initQ(); t != NULL; t = u)
First step: merge implementation { u = t->next; t->next = NULL; putQ(t); }
link merge(link a, link b) t = getQ();
{ struct node head; link c = &head; while (!emptyQ())
while ((a != NULL) && (b != NULL)) { putQ(t); t = merge(getQ(), getQ()); }
if (less(a->item, b->item)) return t;
{ c->next = a; c = a; a = a->next; } }
else
{ c->next = b; c = b; b = b->next; }
c->next = (a == NULL) ? b : a;
return [Link];
}
4.21 4.23
Top-down list mergesort
Split, sort, and merge
link mergesort(link c)
{ link a, b;
if (c->next == NULL) return c;
a = c; b = c->next;
while ((b != NULL) && (b->next != NULL))
{ c = c->next; b = b->next->next; }
b = c->next; c->next = NULL;
return merge(mergesort(a), mergesort(b));
}
4.22