# Merge Sorting in Python

This my implementation of the Merge Sorting Algorithm:

def merge(series1, series2):
output = []
while series1 != [] or series2 != []:
if series1 == []:
output.append(series2)
series2.pop(0)
continue
if series2 == []:
output.append(series1)
series1.pop(0)
continue
last1 = series1
last2 = series2
if last1 <= last2:
series1.pop(0)
output.append(last1)
continue
if last2 < last1:
series2.pop(0)
output.append(last2)
continue
return output

def is_even(x):
if x%2 == 0:
return True
return False

def merge_sort(series):
iseries = []
for i in series:
iseries.append([i])
while len(iseries) > 1:
output = []
length = len(iseries)
if not is_even(length):
length -= 1
for i in range(0, (length-1), 2):
a = iseries[i]
b = iseries[i+1]
output.append(merge(a, b))
output.append(iseries[-1])
else:
for i in range(0, (length-1), 2):
a = iseries[i]
b = iseries[i+1]
output.append(merge(a, b))
iseries = []
iseries += output
return iseries


Basically it splits the items in the initial series into lists of one item (series to iseries). Then I merge the items two-by-two appending the new items to another list (output), and set the main series equals to output. I do this until it's 1 item only and return the 1st item (return iseries).

In merge you are doing list comparison (series1 != [] or series2 != []). This is expensive. You can avoid this by storing the length of two list beforehand and using that value to detect when to come out of the loop.

Also by using a small trick you can avoid using pop() function.

Avoid using continue. You can easily remove it by putting if else condition properly.

Your variable names are not indicating their actual purpose. It is recommended to use meaning names for variables.

def merge(series1, series2):

output = []
len_series1 = len(series1)
len_series2 = len(series2)
pointer_series1 = 0
pointer_series2 = 0

while pointer_series1 < len_series1 and pointer_series2 < len_series2:
last1 = series1[pointer_series1] #the variable name is not indicating the actual task of this variable
last2 = series2[pointer_series2]
if last1 <= last2:
output.append(last1)
pointer_series1 += 1
elif last2 < last1:
output.append(last2)
pointer_series2 += 1

output += series1[pointer_series1:]
output += series2[pointer_series2:]
#the above two statements removes the need to check the emptiness of each list
return output


In is_even function

if x%2== 0


can be rewritten as

if not x%2


The latter one is more 'pythonic'

If I were you I would define a function is_odd instead of is_even, because in the later part of the code you are checking whether a number is odd or not.

merge_sort can also be made more pythonic. The following code actually shows the power of Python to write complicated code in fewer lines:

def merge_sort(series):

iseries = [[i] for i in series]

while len(iseries) > 1:
iseries = [merge(a,b) if b else a for a,b in map(None,*[iter(iseries)]*2) ]
return iseries

# working explained
#iseries = [,,,]
#iter(iseries) returns an iterable object lets say (o1)
# [iter(iseries)]*2 creates a list [o1,o1]
# map(None,[o1,o1]) calls Identity function; the arguments are o1.next() and o1.next()
# so for the first case Identity() is called on  (o1.next()) and  (o1.next())

• awesome review, but can you explain this list comprehension you proposed in the merge_sort() function ? specifically the iter() function. – matheussilvapb May 16 '14 at 16:17
• For map() function the first None argument ensures that identity function is used to build the list. iter() returns an iterable object and *2 creates a list containing two reference to the same object. map calls Identity function on two arguments one from each object of the list. Now since both the objects are same iterable object, the next() function in these objects ensures that alternate elements are passed as arguments. – Pranav Raj May 16 '14 at 17:38
• I have also added some comments in the code to explain the working – Pranav Raj May 16 '14 at 17:44
• Actually your code is not working properly.. I'll edit it – matheussilvapb May 17 '14 at 17:15
• Which part is not working properly? – Pranav Raj May 17 '14 at 17:38

I had to implement merge sort in one of my projects and I implemented it in a better way than in my previous post:

def merge_sort(series):
iseries = [[i] for i in series]
while len(iseries) > 1:
iseries = [merge(a,b) if b else a for a,b in map(None,*[iter(iseries)]*2) ]
return iseries

def merge(A, B):
return(
[(A if A>B else B).pop(0) for i in A+B if len(A) and len(B)>0]
+ A + B
)

print merge_sort([1,2,3,91,22,42,11,4,5,6])


I'll only add ontop of the other responses.

if x%2 == 0:
return True
return False


can be better written as:

return not x%2


Beside that USE COMMENTS. They help even in simple code.