1-1 Introduction to Algorithms

Insertion Sort

• Incremental approach
  

Loop Invariants and the Correctness Proof

• We must show three things about a loop invariant

1. Initialization
2. Maintenance
3. Termination

Loop Invariants

• A condition that is always true for each iteration of a loop
• The subarray $A[1 \dots j-1]$ consists of the elements originally in $A[1 \dots j-1]$ but in ascending order

1. Initialization

• True prior to the first iteration
• When $j=2$, $A[1 \dots j-1]$ consists of the element $A[1]$ which is original one in $A[1]$
  Moreover, the subarray is sorted

2. Maintenance

• If it is true before an iteration of the loop, it remains true before the next iteration
• The subarray $A[1 \dots j]$ consists of the elements originally in $A[1 \dots j]$ in sorted order
• Incrementing $j$ for the next iteration of the for loop preserves the loop invariant

3. Termination

• When the loop terminates, show that the algorithm is correct
• When $j=n+1$, the for loop terminates
• We have that $A[1\dots n]$ consists of the elements originally in $A[1\dots n]$ but in ascending order
• Hence the entire array is sorted, which means that the algorithm is correct

---

Divide and Conquer

Solve a problem recursively by applying three steps at each level of the recursion

• Divide the problem into a number of subproblems
• Conquer the subproblem by solving them recursively
• Combine the solutions to the subproblems into the solution for the original problem

Merge Sort

• Divide
  • Divide the $n$-element sequence to be sorted into two subsequences of $n/2$ elements each
  • Compute the middle of the subarray, which takes $\Theta(1)$ time
• Conquer
  • Sort the two subsequences recursively using merge sort
  • Recursively solve two subproblems each of size $n/2$, which contribute $2T(n/2)$ to the running time
• Combine
  • Merge the two sorted subsequences to produce the sorted answer
  • Take $\Theta(n)$ time
• The recursion bottoms out when the sequence has length 1, every sequence of length 1 is already in sorted order
• Running time $T(n)$ is $2T(n/2)+n)$

MERGE Procedure

• Assume that the subarrays $A[p\dots q]$ and $A[q+1\dots r]$ are in sorted order
• Merge them to form a single sorted subarray that replaces the current subarray $A[p \dots r]$
• $MERGE(A,p,q,r)$ where $A$ is an array and $p,q,r$ are indices into the array such that $p \leq q < r$

Loop Invariant and the Correctness Proof

Loop Invariant

• At the start of each iteration, the subarray $A[p \dots k-1]$ contains the $(k-p)$ smallest elements
• $L[i]$ and $R[j]$ are the smallest elements of their arrays that have not been copied back into $A$

Initialization

• We have $k=p$, so the subarray $A[p \dots k-1]$ is empty
• Since $i=j=1$, both $L[i]$ and $R[j]$ are the smallest elements of their arrays that have not been copied back into $A$

Maintenance

• When $L[i] \leq R[j]$
  • $L[i]$ is the smallest element
  • After line 14, the subarray will contain the $k-p+1$ smallest elements
  • Incrementing $k$ and $i$ reestablishes the loop invariant for the next iteration
• When $L[i] > R[j]$
  • Line 16, 17 perform the appropriate action

Termination

• At termination, $k=r+1$
• The subarray $A[p \dots r]$ contains smallest elements of $L$ and $R$ in sorted order