How might we make this Python Merge Sort implementation more Pythonic?

Question

I've implemented a (version of) Merge Sort algorithm in Python. My goal here is two-fold:

1. Improve understanding of Merge Sort and recursion in a language agnostic way.
2. Improve understanding of Python conventions and idioms.

The implementation recursively splits the given sequence into left and right sequences and then merges the two subsequences back together sorted in ascending order.

All suggestions for improvement are welcome. I'd especially like feedback on the following:

• looping through total length of sequence and the unused variable.
• use of try-except blocks.
• use of indexing and slicing.

---

class MergeSort(object):

def sort(self, seq):
    '''
    Sorts a sequence of integers.

    @param seq: an unsorted tuple or list.
    @return:    a new tuple with elements in @seq sorted in ascending order. 
    '''
    if(len(seq) <= 1):
        return seq
    else:
        return self._merge(leftSortedSeq=self.sort(seq[0:(len(seq) / 2)]), 
                           rightSortedSeq=self.sort(seq[(len(seq) / 2):]))

def _merge(self, leftSortedSeq, rightSortedSeq):
    if(len(leftSortedSeq) == 0):
        return rightSortedSeq
    elif(len(rightSortedSeq) == 0):
        return leftSortedSeq

    leftPointer = 0
    rightPointer = 0
    mergedSeq = []
    mergedSeqLength = len(leftSortedSeq) + len(rightSortedSeq)
    for elementNumber in range(mergedSeqLength):

        try:
            smallestInLeft = leftSortedSeq[leftPointer]
        except IndexError:
            mergedSeq += rightSortedSeq[rightPointer:]
            return tuple(mergedSeq)

        try:
            smallestInRight = rightSortedSeq[rightPointer]
        except IndexError:
            mergedSeq += leftSortedSeq[leftPointer:]
            return tuple(mergedSeq)

        if(smallestInLeft < smallestInRight):
            mergedSeq.append(leftSortedSeq[leftPointer])
            leftPointer += 1
        else:
            mergedSeq.append(rightSortedSeq[rightPointer])
            rightPointer += 1

    return tuple(mergedSeq)

Answer 1

Empty lists are "false"

When you check if a list is empty or not, you don't need to write like this:

if len(left_sorted_seq) == 0:
    # empty list

You can write simply:

if not left_sorted_seq:
    # empty list

Exceptions are slow, only use for unexpected events

This is slower:

try:
    smallestInLeft = leftSortedSeq[leftPointer]
except IndexError:
    mergedSeq += rightSortedSeq[rightPointer:]
    return tuple(mergedSeq)

compared to this:

if leftPointer < len(leftSortedSeq):
    smallestInLeft = leftSortedSeq[leftPointer]
else:
    mergedSeq += rightSortedSeq[rightPointer:]
    return tuple(mergedSeq)

Exceptions are good for handling situations that normally should not happen. For example trying to insert a duplicate primary key into a database table is clearly some sort of mistaken operation, and exception handling is appropriate for that. In your sorting algorithm, reaching the end of the left or right sequence is perfectly normal, and is very much expected to happen during normal operations. If you benchmark your program with many iterations and sorting over larger sets, the time difference will be big.

Don't convert objects if you don't have to

This conversion to tuple is unnecessary:

return tuple(mergedSeq)

So don't do it. This will work just fine, and slightly faster:

return mergedSeq

Rename unused variables to _

In the main loop you're not using elementNumber for anything. I like to rename these kind of variables to _. Although, an unused variable is usually a hint that perhaps there's a better way of doing things, like the algorithm suggested by @PranavRaj.

Follow PEP8

PEP8 is the official style guide to Python. I recommend to follow it. You can install the pep8 command line tool with pip, it can detect all coding style violations recursively in your project directory.

Extra tricks for speed

Here's a slightly faster version of Pranav's solution:

left_i = 0
right_i = 0
left_sorted_len = len(left_sorted_seq)
right_sorted_len = len(right_sorted_seq)
merged = []
append = merged.append

while left_i < left_sorted_len and right_i < right_sorted_len:
    smallestInLeft = left_sorted_seq[left_i]
    smallestInRight = right_sorted_seq[right_i]

    if smallestInLeft < smallestInRight:
        append(smallestInLeft)
        left_i += 1
    else:
        append(smallestInRight)
        right_i += 1

if left_i < left_sorted_len:
    return merged + left_sorted_seq[left_i:]
return merged + right_sorted_seq[right_i:]

What makes this faster:

• Pranav already precalculated the list lenghts (I renamed to left_sorted_len and right_sorted_len, following PEP8) but did not explain: doing so makes the loop faster, because len(...) is only evaluated once.
• Notice the caching of merged.append method as append, to reduce the number of method lookups
• Notice the return statements, split to two cases to avoid concatenating empty slices

I measured differences in speed using 10 iterations of sorting a random sequence of 1000 numbers. You probably don't have to optimize this to the maximum, that's why I made this the last point of my post, more as additional information rather than a real recommendation.

Answer 2

If you have any expression like the one below

if(x == 0) 

then you can rewrite it as

if not x

You can get rid of parenthesis and can make it more pythonic by writing like this.

Similarly you an rewrite :

if(len(leftSortedSeq) == 0):
    return rightSortedSeq
elif(len(rightSortedSeq) == 0):
    return leftSortedSeq

as

if not len(leftSortedSeq):
    return rightSortedSeq
elif not len(rightSortedSeq):
    return leftSortedSeq

If I were you I would avoid using excetions for the cases which can be avoided using simple if else. This will give the code more clarity.

We can avoid the exception by changing the code a bit.

I have also avoided conversion to tuple. The concatenation of tuple and list may cause problems. So its better to avoid unnecessary conversions.

lenLeftSeq = len(leftSortedSeq)
lenRightSeq = len(rightSortedSeq)

while leftPointer < lenLeftSeq and rightPointer < lenRightSeq:

    smallestInLeft = leftSortedSeq[leftPointer]
    smallestInRight = rightSortedSeq[rightPointer]

    if(smallestInLeft < smallestInRight):
        mergedSeq.append(smallestInLeft)
        leftPointer += 1
    else:
        mergedSeq.append(smallestInRight)
        rightPointer += 1

return mergedSeq +
             leftSortedSeq[leftPointer:] +
             rightSortedSeq[rightPointer:]