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.

# Code for the merge subroutine | |

def merge(a,b): | |

""" Function to merge two arrays """ | |

c = [] | |

while len(a) != 0 and len(b) != 0: | |

if a[0] < b[0]: | |

c.append(a[0]) | |

a.remove(a[0]) | |

else: | |

c.append(b[0]) | |

b.remove(b[0]) | |

if len(a) == 0: | |

c += b | |

else: | |

c += a | |

return c | |

# Code for merge sort | |

def mergesort(x): | |

""" Function to sort an array using merge sort algorithm """ | |

if len(x) == 0 or len(x) == 1: | |

return x | |

else: | |

middle = len(x)/2 | |

a = mergesort(x[:middle]) | |

b = mergesort(x[middle:]) | |

return merge(a,b) |

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

You must use a floor function in line 26, otherwise is gives an error.

TypeError: slice indices must be integers or None or have an

indexmethodLikeLike

or simply: len(x)//2

LikeLike

die

LikeLike

I see you don’t monetize your site, don’t waste your

traffic, you can earn additional bucks every month because you’ve

got high quality content. If you want to know how to make extra $$$,

search for: Boorfe’s tips best adsense alternative

LikeLike

You should not be using the “a.remove(a[0])” and “b.remove(b[0])”. Removing from the head of a list is O(n) and you are doing it n times so it is quadratic.

Maybe something like:

would be better?

LikeLike

I believe it doesn’t matter …. you are using/ creating a variable i_a and i_b and doing an increment everytime same as .remove[0] done by the author (constant time).

But In one case your algorithm takes more time than the authors …

Your while loop runs longer when one of a or b is done sorting first …

Proof:

because if all elements in a are sorted first (len(a) == i_a)

Author: His algorithm takes the remaining elements in b and puts them in c in one single attempt

Yours: Keeps running till len(b) ==i_b

and vice versa in case you finish sorting b before a

LikeLike

fast head pops?

https://docs.python.org/3/library/collections.html#collections.deque

LikeLike

pretty neat

LikeLike