4
\$\begingroup\$
def mergesort( array ):
    # array is a list

    #base casee
    if len(array) <= 1:
        return array
    else:
        split = int(len(array)/2)
        #left and right will be sorted arrays
        left = mergesort(array[:split])
        right = mergesort(array[split:])

        sortedArray  = [0]*len(array)

        #sorted array "pointers"
        l = 0
        r = 0

        #merge routine
        for i in range(len(array)):

            try:
                #Fails if l or r excede the length of the array
                if left[l] < right[r]:
                    sortedArray[i] = left[l]
                    l = l+1
                else:
                    sortedArray[i] = right[r]
                    r = r+1
            except:
                if r < len(right):
                    #sortedArray[i] = right[r]
                    #r = r+1
                    for j in range(len(array) - r-l):
                        sortedArray[i+j] = right[r+j]
                    break
                else:
                    #sortedArray[i] = left[l]
                    #l = l+1
                    for j in range( len(array) - r-l):
                        sortedArray[i+j] = left[l+j]
                    break

        return sortedArray
\$\endgroup\$
  • \$\begingroup\$ I'm confused, I thought a merge sort would always take 2 lists as input and return one list as output. \$\endgroup\$ – pacmaninbw Sep 13 '16 at 17:21
  • \$\begingroup\$ @pacmaninbw I don't believe so. Merge sort is an algorithm for taking an unsorted list and turning it into a sorted list. There is a main section of merge sort called the merge where two sorted lists are combined into one sorted list. In my code the two sorted lists are "left" and "right" \$\endgroup\$ – MattTheSnake Sep 13 '16 at 18:59
2
\$\begingroup\$

First of all, the code suffers a very typical problem. The single most important feature of merge sort is stability: it preserves the order of the items which compare equal. As coded,

            if left[l] < right[r]:
                sortedArray[i] = left[l]
                l = l+1
            else:
                sortedArray[i] = right[r]
                r = r+1

of two equals the right one is merged first, and the stability is lost. The fix is simple:

            if left[l] <= right[r]:

(or if right[i] < left[i]: if you prefer).


I don't think that try/except on each iteration is a way to go. Consider

        try:
            while i in range(len(array)):
                ....
        except:
            ....

Of course here i is not known in the except clause. Again, the fix is simple. Notice that the loop is never terminated by condition: either left or right is exhausted before i reaches limit. It means that testing the condition is pointless, and i is an index on the same rights as l and r:

        l = 0
        r = 0
        i = 0
        try:
            while True:
                ....
        except:
            ....

Naked except are to be avoided. Do except IndexError: explicitly.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions! I tested out the changes you suggested and I got about a 0.3s improvement on an original 7.1s time for sorting a list of of 1 million random integers. I understand the second suggestion but I don't get the first one. Is the first suggestion important when its not just integers your sorting? I was able to use this suggestion to make my inversion counting algorithm more robust. \$\endgroup\$ – MattTheSnake Sep 14 '16 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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