Divide and Conquer

Sorting & Inversions

Sorting Problem

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

How many sorting algorithms
you know?
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 10
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 5 10
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 5 10 26
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 3 5 10 26
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 3 4 5 10 26
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 3 4 5 10 16 26
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 3 4 4 5 10 16 26
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
– How fast is it?

1 10 5 26 3 4 16 4 2

1 2 3 4 4 5 10 16 26
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one. How many number
– How fast is it? we should insert?

1 10 5 26 3 4 16 4 2

1 2 3 4 4 5 10 16 26

How long it takes to

insert one number?
Insertion Sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 1:
– Try Insertion Sort: fix the output one by one.
𝑛 numbers
– How fast is it?

1 10 5 26 3 4 16 4 2

1 2 3 4 4 5 10 16 26

At most 𝑛 operations
Don’t forget the correctness!

▪ Is it correct?
▪ How to prove it!
– Using Induction?
Prove correctness by induction.

▪ Base Case
– If we only insert one integer, it is sorted.

▪ Induction
– Assume the list is sorted after the 𝑘 − 1-th insertion.
– Prove the list is sorted after the 𝑘-th insertion.
– Assume the integer 𝑗 is inserted at location 𝑖.
▪ 𝑗 ≥ 𝑎𝑖 ≥ 𝑎≤𝑖 .
▪ 𝑗 < 𝑎𝑖+1 ≤ 𝑎≥𝑖+1 .
 Big
Problem

Small Small
Problem Problem

Smaller Smaller Smaller Smaller

Problem Problem Problem Problem

Ok! Let’s move to divide and

conquer!
Divide and Conquer

▪ Recall the divide and conquer

▪ Divide
– Divide the problem into small size subproblems.

▪ Recurse
– Solve the small size subproblems.

▪ Combine
– Combine the output of small size subproblems to get the answer of
the original problem.
▪ Basic solver
– If the problem size is small enough, we should solve it directly.
Merge sort

▪ Input: A set of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: The same set of 𝑛 integers in ascending order.

▪ Plan 2: Divide and Conquer (Merge Sort)
– Divide: Dive the input into two subsets:
▪ 𝑥1 , 𝑥2 , … , 𝑥𝑛/2 ; 𝑥𝑛/2+1 , 𝑥𝑛/2+2 , … , 𝑥𝑛
– Recurse: Sort two subsets (smaller size problems).
▪ Let 𝑦1 , 𝑦2 , … , 𝑦𝑛/2 ; 𝑦𝑛/2+1 , 𝑦𝑛/2+2 , … , 𝑦𝑛 be the output (sorted list).
– Combine: Merge to sorted list to one long sorted list.
Merge Sort

1 10 5 26 3 4 16 4 2
Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16

4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 2 4

4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 2 4

4 2
 Merge Sort

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 2 4 16

1 10 5 26 3 4 16 2 4

4 2
 Merge Sort

1 5 10 26 2 3 4 4 16

1 10 5 26 3 4 2 4 16

1 10 5 26 3 4 16 2 4

4 2
 Merge Sort

1 2 3 4 4 5 10 16 26

1 5 10 26 2 3 4 4 16

1 10 5 26 3 4 2 4 16

1 10 5 26 3 4 16 2 4

4 2
What is the next?
The remaining questions

▪ How to merge two sorted lists?

▪ How fast we can make it?
Merge two sorted lists

▪ Input: two sorted lists 𝐴 = 𝑎1 , 𝑎2 , … , 𝑎𝑛 , 𝐵 = 𝑏1 , 𝑏2 , … , 𝑏𝑚

▪ Output: a sorted list 𝐶
▪ Straightforward Plan
– Insert each 𝑏 into 𝐴 iteratively.
– Time:
▪ 𝑚 integer to insert.
▪ 𝑛 times for each insertion.
– Totally: 𝑂 𝑚𝑛 Do we really need so
many comparisons?
– Merge Sort:
𝑛
▪ 𝑇 𝑛 = 2𝑇 + 𝑂(𝑛2 /4)
2
Merge two sorted lists

▪ Input: two sorted lists 𝐴 = 𝑎1 , 𝑎2 , … , 𝑎𝑛 , 𝐵 = 𝑏1 , 𝑏2 , … , 𝑏𝑚

▪ Output: a sorted list 𝐶
▪ Smarter Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2 3

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2 3 4

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2 3 4 4

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2 3 4 4 5

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶.
Example

1 5 10 26 2 3 4 4 16

1 2 3 4 4 5 10

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2 3 4 4 5 10 16

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
Example

1 5 10 26 2 3 4 4 16

1 2 3 4 4 5 10 16 26

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶.
Is it correct?
Prove by induction.
Is Merge Sort correct?
Prove by induction.
How fast is the algorithm?

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶

▪ Analysis 1
– 𝑖 at most move 𝑛 times.
– 𝑗 at most move 𝑚 times for one 𝑖 move.
– 𝑂 𝑛𝑚 ?
How fast is the algorithm?

▪ Analysis 1
– 𝑖 at most move 𝑛 times.
– 𝑗 at most move 𝑚 times for one 𝑖 movement.
– 𝑂 𝑛𝑚 ?

▪ Analysis 2
– How many time it takes to append one number to 𝐶?
– 1 number → 1 comparison!
Charging Argument!
– Output 𝑚 + 𝑛 numbers → 𝑚 + 𝑛 comparisons!
– A linear time algorithm!
– 𝑶(𝒏 + 𝒎)
Finally…

▪ What is the running time of merge sort?

– Equip the linear time combining into merge sort.
– Assume merge sort runs 𝑇(𝑛) time to sort a size 𝑛 list.
– What is 𝑇 𝑛 ?
𝑛 𝑛
𝑛 +
– 𝑇 𝑛 = 2𝑇 + 𝑂(𝑛) 2 2
2

▪ I believe you know it is 𝑂 𝑛 log 𝑛 ! But, why?

 𝑛
𝑇 𝑛 =𝑇 + O(n)
2

An efficient tool to
calculate these expressions
Master Theorem

▪ Master Theorem
𝑛
– If 𝑇 𝑛 = 𝑎𝑇 + 𝑂 𝑛𝑑
𝑏

𝑂 𝑛𝑑 𝑎 < 𝑏𝑑
–𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
How to understand it?
Understand the parameters

▪ Master Theorem
𝑛 Divide into 𝑎
– If 𝑇 𝑛 = 𝒂𝑇 + 𝑂 𝑛𝒅
𝒃 problems

𝑂 𝑛𝑑 𝑎 < 𝑏𝑑
–𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
Understand the parameters

▪ Master Theorem
𝑛 Divide into 𝑎
– If 𝑇 𝑛 = 𝒂𝑇 + 𝑂 𝑛𝒅
𝒃 problems
Subproblem
𝑂 𝑛𝑑 𝑎< 𝑏𝑑 size: 𝑛/𝑏

–𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
Understand the parameters
Combining
▪ Master Theorem cost: 𝑂(𝑛𝑑 )
𝑛 Divide into 𝑎
– If 𝑇 𝑛 = 𝒂𝑇 + 𝑂 𝑛𝒅
𝒃 problems
Subproblem
𝑂 𝑛𝑑 𝑎< 𝑏𝑑 size: 𝑛/𝑏

–𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
Running time of merge sort

▪ Recall
– Merge sort divides the problem to two 𝒏/𝟐-size problems.
– Merging two 𝑛/2-size sorted lists takes 𝑶 𝒏 times.
𝑛
– 𝑇 𝑛 = 2𝑇 + 𝑂(𝑛)
2

▪ Use Master Theorem

𝑂 𝑛𝑑 𝑎 < 𝑏𝑑
𝑛
– If 𝑇 𝑛 = 𝒂𝑇 + 𝑂 𝑛𝒅 , then 𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑 .
𝒃
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
– 𝑎 = 2, 𝑏 = 2, 𝑑 = 1
– 𝑇 𝑛 = 𝑂(𝑛 log 𝑛)
 Understand the formula & proof

Level 0 𝑛 1 problem

𝑛 𝑛 𝑛
Level 1 𝑏 𝑏 𝑏
𝑎 problems

𝑛 𝑛 𝑛 𝑛
Level 2 𝑏2 𝑏2
…… 𝑏2 𝑏2
𝑎2 problems

𝑛 𝑛 𝑛 𝑛
Level k 𝑏𝑘 𝑏𝑘
…… 𝑏𝑘 𝑏𝑘
𝑎𝑘 problems

Level log 𝑏 𝑛 1 1 …… 1 1 𝑎log𝑏 𝑛 problems

Understand the formula & proof

▪ The running time of solving all size-1 problem is

– 𝑎log𝑏 𝑛 ⋅ 𝑂 1 = 𝑂(𝑛log𝑏 𝑎 ）

▪ The total running time is

𝑛 𝑑 𝑛 𝑑
– 𝑂 𝑛𝑑 +𝑎⋅𝑂 + ⋯+ 𝑎𝑘 ⋅𝑂 + ⋯ + 𝑎log𝑏 𝑛 ⋅ 𝑂 1
𝑏 𝑏𝑘

▪ Simplification 𝑛

𝑛 𝑛 𝑛
𝑎 𝑎 𝑘 𝑎 log𝑏 𝑛
– 𝑂 𝑛𝑑 ⋅ (1 + + ⋯+ + ⋯+ ) 𝑏 𝑏 𝑏
𝑏𝑑 𝑏𝑑 𝑏𝑑 𝑛 𝑛 𝑛 𝑛
𝑏2 𝑏2
…… 𝑏2 𝑏2

𝑛 𝑛 𝑛 𝑛
𝑛= 𝑏 log𝑏 𝑛 𝑏𝑘 𝑏𝑘
…… 𝑏𝑘 𝑏𝑘

1 1 …… 1 1
Case 1: 𝑎 < 𝑏 𝑑

𝑂 𝑛𝑑 𝑎 < 𝑏𝑑
▪ 𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
𝑎 𝑎 𝑘 𝑎 log𝑏 𝑛
▪ 𝑇 𝑛 = 𝑂 𝑛𝑑 ⋅ (1 + 𝑑 + ⋯+ + ⋯+ )
𝑏 𝑏𝑑 𝑏𝑑
𝑛
𝑎
▪ 𝑎 < 𝑏𝑑 → <1
𝑏𝑑 𝑛
𝑏
𝑛
𝑏
𝑛
𝑏

▪ 𝑇 𝑛 = 𝑂 𝑛𝑑 𝑛
𝑏2
𝑛
𝑏2
……
𝑛
𝑏2
𝑛
𝑏2

𝑛 𝑛 𝑛 𝑛
𝑏𝑘 𝑏𝑘
…… 𝑏𝑘 𝑏𝑘

1 1 …… 1 1
Case 2: 𝑎 > 𝑏 𝑑

𝑂 𝑛𝑑 𝑎 < 𝑏𝑑
▪ 𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
𝑎 𝑎 𝑘 𝑎 log𝑏 𝑛
▪ 𝑇 𝑛 = 𝑂 𝑛𝑑 ⋅ (1 + 𝑑 + ⋯+ + ⋯+ )
𝑏 𝑏𝑑 𝑏𝑑
𝑛
𝑎
▪ 𝑎 > 𝑏𝑑 → >1
𝑏𝑑 𝑛
𝑏
𝑛
𝑏
𝑛
𝑏

▪ The last term dominates the sum 𝑛

𝑏2
𝑛
𝑏2
……
𝑛
𝑏2
𝑛
𝑏2

𝑎 log𝑏 𝑛
𝑛 𝑛 𝑛 𝑛
𝑑 𝑑 𝑎log𝑏 𝑛 ……
▪ 𝑇 𝑛 =𝑂 𝑛 =𝑂 𝑛 𝑏𝑘 𝑏𝑘 𝑏𝑘 𝑏𝑘
𝑏𝑑 𝑛𝑑
1 1 …… 1 1

= 𝑂 𝑎log𝑏 𝑛 = 𝑂(𝑛log𝑏𝑎 )
Case 3: 𝑎 = 𝑏 𝑑

𝑂 𝑛𝑑 𝑎 < 𝑏𝑑
▪ 𝑇 𝑛 = 𝑂 𝑛log𝑏 𝑎 𝑎 > 𝑏𝑑
𝑂 𝑛𝑑 log 𝑛 𝑎 = 𝑏𝑑
𝑎 𝑎 𝑘 𝑎 log𝑏 𝑛
▪ 𝑇 𝑛 = 𝑂 𝑛𝑑 ⋅ (1 + 𝑑 + ⋯+ + ⋯+ )
𝑏 𝑏𝑑 𝑏𝑑
𝑛
𝑎
▪ 𝑎 = 𝑏𝑑 → =1
𝑏𝑑 𝑛
𝑏
𝑛
𝑏
𝑛
𝑏

▪ 𝑇 𝑛 = 𝑂 𝑛𝑑 log 𝑏 𝑛 𝑛
𝑏2
𝑛
𝑏2
……
𝑛
𝑏2
𝑛
𝑏2

𝑛 𝑛 𝑛 𝑛
𝑏𝑘 𝑏𝑘
…… 𝑏𝑘 𝑏𝑘

1 1 …… 1 1
Divide and Conquer
Counting Inversions
Counting Inversions

▪ Input: A list of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: number of inversions

▪ Application
– You rank 𝑛 songs.
– Music site consults database to find people with similar tastes.
– What is similar?
▪ My rank: 1, 2, 3, 4, 5, … , 𝑛
▪ Your rank: 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛
▪ Songs 𝑖, 𝑗 are inverted if 𝑖 < 𝑗 but 𝑥𝑖 > 𝑥𝑗 .
▪ Similar metric: number of inversions.
Counting Inversions vs Merge
Sort
Counting Inversions

▪ Input: A list of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: number of inversions

▪ Plan 1: Brute-force
– 𝑶 𝒏𝟐
Counting Inversions

▪ Input: A list of 𝑛 integers

– 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛

▪ Output: number of inversions

▪ Plan 2: Divide and Conquer (Merge Sort Style)
– Divide: Dive the input into two subsets:
▪ 𝑥1 , 𝑥2 , … , 𝑥𝑛/2 ; 𝑥𝑛/2+1 , 𝑥𝑛/2+2 , … , 𝑥𝑛
– Recurse: count inversions in the two subsets.
▪ Let 𝑐1 , c2 be the two numbers.
– Combine: Return the total number of inversions.
▪ Count the inversions across subsets, to be 𝑐3 .
▪ Return 𝑐1 + 𝑐2 + 𝑐3 .
Counting Inversions

1 10 5 26 3 4 16 4 2
Counting Inversions

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2
 Counting Inversions

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2
 Counting Inversions

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

4 2
 Counting Inversions

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

0 0 0 0 0 0 0 1

1 10 5 26 3 4 16 4 2
0 0
4 2
 Counting Inversions

1 10 5 26 3 4 16 4 2

1 10 5 26 3 4 16 4 2

0 0 0 3

1 10 5 26 3 4 16 4 2

0 0 0 0 0 0 0 1

1 10 5 26 3 4 16 4 2
0 0
4 2
 Counting Inversions 19

1 10 5 26 3 4 16 4 2

1 5

1 10 5 26 3 4 16 4 2

0 0 0 3

1 10 5 26 3 4 16 4 2

0 0 0 0 0 0 0 1

1 10 5 26 3 4 16 4 2
0 0
4 2
Count inversions across two lists

▪ Input: two lists 𝐴 = 𝑎1 , 𝑎2 , … , 𝑎𝑛 , 𝐵 = 𝑏1 , 𝑏2 , … , 𝑏𝑚

▪ Output: number of inversions across two lists
▪ Plan
– For each 𝑎𝑖 in 𝐴
▪ Count the number of 𝑏𝑗 < ai in B.
▪ Add the number into total number of inversions.
– Return the total number.
Example

1 10 5 26 3 4 16 4 2

Counter = 0

▪ Plan
– For each 𝑎𝑖 in 𝐴
▪ Count the number of 𝑏𝑗 < ai in B.
▪ Add the number into total number of inversions.
– Return the total number.
Example

1 10 5 26 3 4 16 4 2

Counter = 4

▪ Plan
– For each 𝑎𝑖 in 𝐴
▪ Count the number of 𝑏𝑗 < ai in B.
▪ Add the number into total number of inversions.
– Return the total number.
Example

1 10 5 26 3 4 16 4 2

Counter = 8

▪ Plan
– For each 𝑎𝑖 in 𝐴
▪ Count the number of 𝑏𝑗 < ai in B.
▪ Add the number into total number of inversions.
– Return the total number.
Example

1 10 5 26 3 4 16 4 2

Counter = 13

▪ Plan
– For each 𝑎𝑖 in 𝐴
▪ Count the number of 𝑏𝑗 < ai in B.
▪ Add the number into total number of inversions.
– Return the total number.
Example

1 10 5 26 3 4 16 4 2

Counter = 13

▪ Plan
– For each 𝑎𝑖 in 𝐴
▪ Count the number of 𝑏𝑗 < ai in B.
▪ Add the number into total number of inversions.
– Return the total number.
How long it takes?

▪ Analysis
– Each 𝑎𝑖 , scan the whole list 𝐵.
– It takes 𝑂(𝑛𝑚).

▪ How to improve?
– It become easier when the two lists are sorted!
– Why not do merging and counting together!
Merge & Count

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
𝑎𝑖 > 𝑏𝑗′ , ∀𝑗′ < 𝑗
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
𝑎𝑖′ > 𝑏𝑗′ , ∀𝑗 ′ ≤ 𝑚, ∀𝑖 ′ ≥ 𝑖
Example

1 5 10 26 2 3 4 4 16

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0

1 2

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0

1 2 3

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0

1 2 3 4

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0

1 2 3 4 4

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0 c+=4

1 2 3 4 4 5

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0 c+=4 c+=4

1 2 3 4 4 5 10

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0 c+=4 c+=4

1 2 3 4 4 5 10 16

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
 Example

1 5 10 26 2 3 4 4 16

c+=0 c+=4 c+=4 c+=5

1 2 3 4 4 5 10 16 26

▪ Plan
– Maintain 2 pointers 𝑖 = 1, 𝑗 = 1, and a counter 𝑐 = 0
– Repeat
▪ Append min{𝑎𝑖 , 𝑏𝑗 } to 𝐶
▪ If 𝑎𝑖 is smaller, then move 𝑖 to 𝑖 + 1; If 𝑏𝑗 is smaller, then move 𝑗 to 𝑗 + 1.
▪ If we move 𝑖 to 𝑖 + 1, then 𝑐 = 𝑐 + 𝑗 − 1.
▪ Break if 𝑖 > 𝑛 or 𝑗 > 𝑚
– Append the reminder of the non-empty list to 𝐶
– If 𝑖 ≤ 𝑛, 𝑐 = 𝑐 + 𝑚 ⋅ (𝑛 − 𝑖 + 1)
Try to prove to yourself the
correctness.
How fast is it now?

▪ The same as Merging two sorted listed.

▪ Counting Inversion is as fast as Merge Sort.
𝑛
▪ 𝑇 𝑛 = 2𝑇 + 𝑂 𝑛 = 𝑂(𝑛 log 𝑛)
2
Today’s goal

▪ Learn Insertion Sort and Merge Sort

▪ Learn how to Count Inversions with Merge Sort
▪ Learn to prove the correctness of them
▪ Learn to analyze their running time
– Charging Argument

▪ Learn the Master Theorem