implement a merge sort

1 files changed, 25 insertions, 1 deletions

diff --git a/notes.md b/notes.md
index dcc1a74..eb58099 100644
--- a/notes.md
+++ b/notes.md
@@ -730,7 +730,7 @@ Analysis of merge sort
 
 ```plaintext
               -----------------------
-              |3|41|52|26|38|57|9|49|
+              |3|9|26|38|41|49|52|57|
               -----------------------
                /                  \
       ------------             ------------
@@ -783,3 +783,27 @@ for k = k to r
     A[k] = R[j]
     j = j + 1
 ```
+
+2.3-3: Use mathematical induction to show that when `n` is an exact power of 2,
+the solution of the recurrence ... is `T(n) = nlg(n)`
+
+```plaintext
+         2            if n = 2
+T(n) = { 2T(n/2) + n  if n = 2**k, for k > 1
+```
+
+ ???
+
+2.3-4: We can express insertion sort as a recursive procedure as follows In
+order to sort `A[i..n]`, we recursively sort `A[i..n-1]` and then insert `A[n]`
+into the sorted array `A[1..n-1]`. Write a recurrence for the worst-case running
+time of this recursive version of insertion sort.
+
+
+2.3-5: Referring back to the searching problem (see Exercise 2.1-3), observe that
+    if the sequence A is sorted, we can check the midpoint of the sequence
+    against v and eliminate half of the sequence from further consideration. The
+    binary search algorithm repeats this procedure, halving the size of the
+    remaining portion of the sequence each time. Write pseudocode, either
+    iterative or recursive, for binary search. Argue that the worst case running
+    time of binary search is O(lg(n)).