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
Jamal's user avatar
Jamal
35.2k13 gold badges134 silver badges238 bronze badges
askedSep 13, 2016 at 17:01
MattTheSnake's user avatar
\$\endgroup\$
2
  • \$\begingroup\$I'm confused, I thought a merge sort would always take 2 lists as input and return one list as output.\$\endgroup\$CommentedSep 13, 2016 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\$CommentedSep 13, 2016 at 18:59

1 Answer1

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 theright one is merged first, and the stability is lost. The fix is simple:

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

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

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

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

Of course herei is not known in theexcept clause. Again, the fix is simple. Notice that the loop isnever terminated by condition: eitherleft orright is exhausted beforei reaches limit. It means that testing the condition is pointless, andi is an index on the same rights asl andr:

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

Nakedexcept are to be avoided. Doexcept IndexError: explicitly.

answeredSep 14, 2016 at 2:25
vnp's user avatar
\$\endgroup\$
1
  • \$\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\$CommentedSep 14, 2016 at 14:07

You mustlog in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.