Merge Sorting in Python

Question

This my implementation of the Merge Sorting Algorithm:

def merge(series1, series2):
    output = []
    while series1 != [] or series2 != []:
        if series1 == []:
            output.append(series2[0])
            series2.pop(0)
            continue
        if series2 == []:
            output.append(series1[0])
            series1.pop(0)
            continue
        last1 = series1[0]
        last2 = series2[0]
        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[0]

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 1^st item (return iseries[0]).

Answer 1

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[0]

# working explained
#iseries = [[1],[2],[3],[4]]
#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 [1] (o1.next()) and [2] (o1.next())

Answer 2

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[0]

 def merge(A, B):
    return(
           [(A if A[0]>B[0] 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])

Answer 3

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.