3
\$\begingroup\$

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

\$\endgroup\$

3 Answers 3

3
\$\begingroup\$

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())
\$\endgroup\$
7
  • 1
    \$\begingroup\$ awesome review, but can you explain this list comprehension you proposed in the merge_sort() function ? specifically the iter() function. \$\endgroup\$ May 16, 2014 at 16:17
  • \$\begingroup\$ 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. \$\endgroup\$
    – Pranav Raj
    May 16, 2014 at 17:38
  • \$\begingroup\$ I have also added some comments in the code to explain the working \$\endgroup\$
    – Pranav Raj
    May 16, 2014 at 17:44
  • \$\begingroup\$ Actually your code is not working properly.. I'll edit it \$\endgroup\$ May 17, 2014 at 17:15
  • \$\begingroup\$ Which part is not working properly? \$\endgroup\$
    – Pranav Raj
    May 17, 2014 at 17:38
2
\$\begingroup\$

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])
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.