# CS341 Lecture Notes - Merge Sort, Quicksort, Binary Search Algorithm

28 views8 pages

16 Oct 2011

School

Department

Course

Professor

1

Divide and Conquer

• MergeSort

– We are given a list of n elements.

– Split list into two lists each of length n/2.

• More precisely, one with length: the other: .

– Sort each list using merge sort (recursive call).

– Merge the sorted lists to get the final result.

• Merge sort analysis:

– Let T(n)= number of comparisons to sort nitems in the

worst case. Note: T(1) = 0, T(2) = 1

• Now what???

0 if 1

( )

( ) if 1

2 2

n

T n n n

T T n n

=

=

+ + Θ >

2

n

2

n

Floors and Ceilings

• In practice, floors and ceilings are often

neglected.

• To be mathematically precise, we should not

neglect them.

• This can nearly always be done, but details

can get quite messy.

• In this

course, we will almost always gloss over

them. This is fine for our purposes, but in other

settings it might not be (e.g. when writing a

formal proof for publication).

2

Solving Recurrences

• Method 1: Recursion Trees

• Method 2: Master theorem

• Method 3: Guessing and Checking method

• We will study these in the next unit. For now,

we solve the recurrence in an ad-hoc fashion.

Simple Merge Sort Analysis

• A simple analysis gives us a good guess:

–Assume n = 2k. Then:

T(n) < cn + 2T(n/2) < cn + 2{cn/2+ 2T(n/4)}

<2cn + 4T(n/4) = ... (continuing)

< icn + 2iT(n/2i)(in general)

< kcn + n T(1) (when iis finally k)

T(n)∈

∈∈

∈O(nlog n)(since k = log n).

3

A More Thorough Analysis

• Write it as

( ) ( )

0 if 1

( )

/2 / 2 if 1

n

T n

T n T n an n

=

≤

+ + >

• Prove T(n)< cn log nby induction on n.

• Base case: n = 1. True since T(n) = 0.

• Inductive step: assume T(k)< ck log k

for k < n,and prove true for k = n.

Mergesort (cont.)

( ) 2 2

log log

2 2 2 2

log log

2 2 2

(log 1) log

2 2

log 2

1

log 2 2

n n

T n T T an

n n n n

c c an

n n n

c c n an

n n

c n c n an

n

cn n c an

n

cn n c an

≤ + +

≤ + +

≤ + +

≤ − + +

= − +

≤ − − +

log

2 2

log for, say, 4

c c

cn n a n

cn n c a

= + − +

≤ =