what is the inductive step for this problem $($mergesort$)$ It works

Inductive hypothesis:

$"$In every the recursive call on an array of length

at most i$,$ MERGESORT returns a sorted array."

Base case $(i=1)$: a $1-$element

array is always sorted.

Inductive step: Need to show:

If $L$ and $R$ are sorted, then

MERGE$($L$,$R$)$ is sorted.

Conclusion: In the top

recursive call, MERGESORT

returns a sorted array.

Fill in the inductive step! $($Either do it

yourself or read it in CLRS Section $2\mathrm{.}3\mathrm{.}1!)$

CSE $100$ LO$3$ Sorting $72$

Assume that $n$ is a power of $2$

for convenience.

Not technically a "loop

invariant," but a

"recursion invariant,"

that should hold at the

beginning of every

recursive call.

MERGESORT$($A$)$:

$n=$ length$($A$)$

if $n1$ :

return $A$

$L=$ MERGESORT$($A$[1$:n$/2])$

$R=$MERGESORT$(A[\frac{n}{2}+1$:$n])$

return MERGE$($L$,$R$)$

Formally: induction

A "loop invariant" is

something that we maintain

Loop invariant$($i$)$: A $[$:i$+1]$ is sorted.

at every iteration of the

algorithm.

Inductive Hypothesis:

The loop invariant$($i$)$ holds at the end of the $i^{th}$ iteration $($of the outer loop$).$

Base case $(i=0)$ :

This logic $($see CLRS for

Before the algorithm starts, $A[$:$1]$ is sorted. $$

details$)$

Inductive step:

If the inductive hypothesis holds at step i$,$ it holds at step i$+1$

Aka, if $A[$:$i+1]$ is sorted at step $i,$ then $A[$:$i+2]$ is sorted at step $i+1$

Conclusion:

At the end of the $n-1\text{'}$st iteration $($aka$,$ at the end of the algorithm$),A[$:$n]$

$=A$ is sorted.

That's what we wanted!

$4$

sorted list.