How might we make this Python Merge Sort implementation more Pythonic? I've implemented a (version of) Merge Sort algorithm in Python. My goal here is two-fold:


Improve understanding of Merge Sort and recursion in a language agnostic way.
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) &lt;= 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 &lt; smallestInRight):
            mergedSeq.append(leftSortedSeq[leftPointer])
            leftPointer += 1
        else:
            mergedSeq.append(rightSortedSeq[rightPointer])
            rightPointer += 1

    return tuple(mergedSeq)
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 &lt; lenLeftSeq and rightPointer &lt; lenRightSeq:

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

    if(smallestInLeft &lt; smallestInRight):
        mergedSeq.append(smallestInLeft)
        leftPointer += 1
    else:
        mergedSeq.append(smallestInRight)
        rightPointer += 1

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