add notes on insertion sort

1 files changed, 43 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index b474a52..17129e5 100644
--- a/notes.md
+++ b/notes.md
@@ -223,3 +223,46 @@ Problem 1-1: Comparison of running times
     | 2^n     |          |             |               |                |
     | n!      |          |             |               |                |
     ```
+
+# Chapter 2 Getting Started
+
+
+2.1 Insertion Sort
+
+Solves the sorting problem.
+
+Input: A sequence of `n` numbers `{a1,a2,...,aN}`
+Output: A permutation (reordering) of the input sequence such that: 
+
+  `{a1 <= a2 <= ... <= aN}`
+
+The numbers that we want to sort are known as keys.
+
+e.g.
+
+```plaintext
+
+a. [5, 2, 4, 6, 1, 3]
+    x  i
+b. [2, 5, 4, 6, 1, 3]
+    x  x  i
+c. [2, 4, 5, 6, 1, 3]
+    x  x  x  i
+d. [2, 4, 5, 6, 1, 3]
+    x  x  x  x  i
+e. [1, 2, 4, 5, 6, 3]
+    x  x  x  x  x  i
+f. [1, 2, 3, 4, 5, 6]
+```
+
+```plaintext
+A = {5,2,4,6,1,3}
+
+for j = 2 to A.length
+  key = A[j]
+  i = j - 1
+  while i > 0 and A[i] > key
+    A[i+1] = A[i]
+    i = i - 1
+  A[i+1] = key
+```