Question

Show that mergesort is a stable algorithm by modifiying the algorithm to sort a list of tuples (first and last names) by their second position. (Modify the merge section to break ties) Modify in python

def mergesort(mlist):
if len(mlist) < 2:
return mlist
else:
mid = len(mlist)//2
return merge( mergesort(mlist[:mid]), mergesort(mlist[mid:]))

# merge two sorted lists
def merge(left, right):
if left == []:
return right
elif right == []:
return left
elif left[0] < right[0]:
return [left[0]] + merge(left[1:], right)
else:
return [right[0]] + merge(left, right[1:])

Answer 1

Python code :

The above python code in question can be modified to sort the list with first name and last name by making it stable sort. The code is as given below with output :

======================================

def mergesort(mlist):

if len(mlist) < 2 :

return mlist

else :

mid = int(len(mlist)/2)

return merge(mergesort(mlist[:mid]), mergesort(mlist[mid:]))

def merge(left, right):

if left == [] :

return right

elif right == [] :

return left

elif left[0][0] < right[0][0]:

return [left[0]] + merge(left[1:], right)

elif left[0][0] > right[0][0]:

return [right[0]] + merge(left, right[1:])

elif left[0][0] == right[0][0] :

if(left[0][1] <= right[0][1]):

return [left[0]] + merge(left[1:], right)

else :

return [right[0]] + merge(left, right[1:])

# sort the list

tuple = [("abc", "aaa"), ("abc", "bbb"), ("abc", "aaa"), ("bcd", "aaa"), ("edfg", "abcd"), ("bc", "aaa")]

print("tuple before sorting : "+ str(tuple))

result = mergesort(tuple)

print("list after sorting : "+ str(result))

===============================================

The output of above code :

def mergesort (mlist): if len(mlist) < 2 1 2 return mlist else: mid = int (len (mlist ) /2) return merge(mergesort(mlist[:mid]), mergesort(mlist[mid:] )) 7 def merge(left, right): if left -= [) : 9 return right 10 elif right == [] : 11 12 return left elif left[0][e] < right[0][@]: return [left[e]] merge(left[1:], right) elif left[0][e] right[0][@]: return [right[e]] + merge(left, right[1:]) elif left[0][e] == right[0][0] : if (left[0][1] <= right[0][1]): return [left[e]] + merge(left[1:], right) 13 14 15 16 17 18 19 else 20 return [right[0]] merge(left, right[1:]) 21 22 23 sort the list tuple = [("abc", "aaa"), ("abc", "bbb"), ("abc", "aaa"), ("bcd", "aaa"), ("edfg", "abcd"), ("bc", "aaa")] 24 sorting " str(tuple)) befo 2 mergesort(tuple) print ("list after sorting : "+ str(result)) result 26 27 28

tuple before sorting : [('abc', 'aaa'), ('abc', 'bbb'), ('abc', 'aaa'), ('bcd', 'aaa'), ('edfg', 'abcd'), ('bc', 'aaa')]
list after sorting : [('abc', 'aaa'), ('abc', 'aaa'), ('abc', 'bbb'), ('bc', 'aaa'), ('bcd', 'aaa'), ('edfg', 'abcd')]

if you have any doubts then you can ask in comment section if you find the solution helpful then upvote the answer. Thank you.