MergeSort issue

Python Help
1

Hi! I am a new python user that is working on the function MergeSort.
The pathway that I have found looks as such:

Given a boolean order function ord and an orderable list s of data items,

  1. if s has length 0 or 1, return s; otherwise
  2. split s into two sublists: the “front” sublist s1 and the “back” sublist s2, where s1 and s2 have the same length if the length of s is even or the length of s1 is one more than the length of s2 if the length of s is odd.
  3. Sort each sublist individually by using this Merge Sort algorithm.
  4. Merge together the sorted versions of s1 and s2 to produce a list whose data items are in order in accordance with the order ord. Do this by considering each data expression from s2 in order of appearance and inserting it into s1 at the highest possible index, while preserving the order ord.

I found a way to code it like this, which I believe conceptually works.
def split(s):
l = len(s)
m = l // 2
if l % 2 == 0:
return [s[:m],s[m:]]
else:
return [s[:m+1],s[m+1:]]

def merge(ord,s,t):
final =
si = 0
ti = 0
while si < len(s) and ti < len(t):
if ord(s[si],t[ti]):
final += [s[si]]
si += 1
else:
final += [t[ti]]
ti += 1
final += s[si:]
final += t[ti:]
return final

def mergeSort(ord, s):
return merge(ord, mergeSort(ord, split(s)[0]), mergeSort(ord, split(s)[1]))

Essentially, I create a function merge which merges ord and two lists, then I simply apply to get mergeSort by recursively adding halves of the list (which I get by a function split).

When I tested it on this example mergeSort(lambda x,y: x > y,[1,2,3,4,4,3,2,1]), it worked correctly. However, when I tried another example: mergeSort(lambda p,q: p[1] < q[1], [(‘X’,5),(‘B’,6),(‘P’,4),(‘X’,3),(‘B’,5),(‘P’,3)]), it failed. I believe this could be because of the way I used ord, but I am not sure what the error could be. Can someone please give me a step forward? Thanks!

3

Please fix your Python code portion to be properly formatted and indented so we can check indentation, and possibly copy it to run it and fix it.

Help us help you. Read this link first and learn how to format code so we can help you better. Do not use a screen shot of your code as some of us will copy and paste the code to get it to work for you, so you can learn from this. About the Python Help category You will get more help this way.

Also for multiple conditionals in a statement I enclose them in (parens). Just in case. Like this.

while (si < len(s)) and (ti < len(t)):
2 Likes
4

Hi, sorry about that. I believe this is better. I also think the indentation is correct so far, and I did add the parentheses. Thanks.

def merge(ord,s,t):
    final = []
    si = 0
    ti = 0
    while si < len(s) and ti < len(t):
        if ord(s[si],t[ti]):
            final += [s[si]]
            si += 1
        else:
            final += [t[ti]]
            ti += 1
    final += s[si:]
    final += t[ti:]
    return final

def mergeSort(ord, s):
    return merge(ord, mergeSort(ord, split(s)[0]), mergeSort(ord, split(s)[1]))

To be clear, merge works with two lists as a helper function for mergeSort.

5

I cannot belive this since your definition of mergeSort causes an inifinie recursion (each call of mergeSort calls mergeSort as well!) So, you need some test to break the condition:

def mergeSort(ord, s):
    if len(s)<2: return s
    return merge(ord, mergeSort(ord, split(s)[0]), mergeSort(ord, split(s)[1]))

With that change both

mergeSort(lambda x,y: x > y,[1,2,3,4,4,3,2,1])
# result: [4, 4, 3, 3, 2, 2, 1, 1]

and (if correct quotation marks are used!)

mergeSort(lambda p,q: p[1] < q[1], [('X',5),('B',6),('P',4),('X',3),('B',5),('P',3)])
# result: [('P', 3), ('X', 3), ('P', 4), ('B', 5), ('X', 5), ('B', 6)]

work on my machine.

2 side remarks:

  • split does not need another case for l odd, so the case return [s[:m],s[m:]] would be sufficient.
  • mergeSort computes the split twice. So, the result of the call of split could be stored in a variable first.
2 Likes
6

Thank you for your response. I understand about the problem of infinite recursion.