PYTHON MERGESORT RECURSIVE FUNCTION I am having issues regarding my merge_sort f
ID: 3871577 • Letter: P
Question
PYTHON MERGESORT RECURSIVE FUNCTION
I am having issues regarding my merge_sort function, specifically performing recursive sorting the right sub-list.
The hint that was given for this assignment was:
# if min_ < max_
# calculate mid ((min + max) // 2)
#recursively sort left sub-list
# recursively sort right sub-list
# merge sorted sub-lists
# merge_sort function
"""
:param unsorted_list: The list to be sorted
:param min_: The minimum index to sort from the given list
:param max_: The maximum index to sort from the given list
Returns nothing, the original list is modified so no copy is needed
"""
Merge_sort Function
test_list = [4, 12, 20, 1, 2, 17, 3, 11, 18, 1]
merge_sort(test_list, 0, len(test_list) - 1)
def merge_sort(unsorted_list, min_, max_):
mid_ = (min_ + max_) // 2
if min_ < max_:
merge_sort(unsorted_list, min_, mid_)
merge(unsorted_list, min_, mid_)
return merge_sort(unsorted_list, mid_ + 1, max_)
merge(unsorted_list, mid_ + 1, max_)
Testing my function with the test list above yields:
[1, 2, 4, 12, 20, 17, 3, 11, 18, 1]
which indicates that the left sublist is working but not the right sublist.
What the expected output should return:
[1, 1, 2, 3, 4, 11, 12, 17, 18, 20]
Explanation / Answer
def merge_sort(unsorted_list,min_,max_):
ret = []
if( len(unsorted_list) == 1):
return unsorted_list;
mid_=(min_+max_)/2
lower = merge_sort(unsorted_list,min_,mid_)
upper = merge_sort(unsorted_list,mid_,max_)
lower_len = len(lower)
upper_len = len(upper)
i = 0
j = 0
while i != lower_len or j != upper_len:
if( i != lower_len and (j == upper_len or lower[i] < upper[j])):
ret.append(lower[i])
i += 1
else:
ret.append(upper[j])
j += 1
return ret
test_list = [4, 12, 20, 1, 2, 17, 3, 11, 18, 1]
ar = merge_sort(test_list,0,len(test_list)-1)
print " ".join(str(x) for x in ar)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.