I have just begun working on a MOOC on algorithms offered by Stanford. Since this course gives us the liberty to choose a programming language, there isn’t any code discussed in those lectures. I plan to convert any algorithm discussed in those lectures into Python code. Since Merge Sort was the first algorithm discussed, I’m starting with that.

Merge Sort is supposedly a good introduction to divide and conquer algorithms, greatly improving upon selection, insertion and bubble sort techniques, especially when input size increases.

**Pseudocode:**

**— Recursively sort the first half of the input array.**

**— Recursively sort the second half of the input array.**

**— Merge two sorted sub-lists into one list.**

C = output [length = n]

A = 1st sorted array [n/2]

B = 2nd sorted array [n/2]

i = 0 or 1 (depending on the programming language)

j = 0 or 1 (depending on the programming language)

*for k = 1 to n*

*if A(i) < B(j)*

* C(k) = A(i)*

* i = i + 1*

*else if A(i) > B(j)*

* C(k) = B(j)*

* j = j + 1*

Note: the pseudocode for the merge operation ignores the end cases.

Visualizing the algorithm can be done in 2 stages — first, the recursive splitting of the arrays, 2 each 2 at a time, and second, the merge operation.

Here’s the Python code to merge sort an array.

We can divide a list in half **log _{2} **

*times where*

**n****is the length of the list. The second process is the**

*n***merge**. Each item in the list will eventually be processed and placed on the sorted list. So the merge operation which results in a list of size

**requires**

*n***operations. The result of this analysis is that**

*n***log**

_{2}*splits, each of which costs*

**n****n**for a total of

**nlog**operations.

_{2}*n***Other Algorithms:**

Karatsuba Integer Multiplication Algorithm

Quick Sort Python Code