# python - Python Merge Sort Recursive

``````# 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函数

``````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_)

test_list = [4, 12, 20, 1, 2, 17, 3, 11, 18, 1]

merge_sort(test_list, 0, len(test_list) - 1)
``````

``````[1, 2, 4, 12, 20, 17, 3, 11, 18, 1]
``````

``````[1, 1, 2, 3, 4, 11, 12, 17, 18, 20]
``````

``````def merge(unsorted_list, min_, max_):
# mid position = start of second sub-list
mid = ((min_   max_) // 2)   1

position1 = min_
position2 = mid
position3 = 0

temp = []
stop = False
while stop == False and position2 < len(unsorted_list) and position1 < mid:
if unsorted_list[position1] <= unsorted_list[position2]:
temp.append(unsorted_list[position1])
position1  = 1
position3  = 1
else:
temp.append(unsorted_list[position2])
position2  = 1
position3  = 1

if position1 >= position2:
for k in range(position1, mid   1):
temp.append(unsorted_list[k])
position2  = 1
position3  = 1
stop = True
if position3 == len(unsorted_list):# temp
for i in range(len(temp)):
unsorted_list[min_] = temp[i]
min_  = 1
elif position2 > max_:
for k in range(position1, mid):
temp.append(unsorted_list[k])
position3  = 1
stop = True
if position3 == len(unsorted_list):# temp
for i in range(len(temp)):
unsorted_list[min_] = temp[i]
min_  = 1

if position3 != len(unsorted_list):
for k in range(position2, len(unsorted_list)):
temp.append(unsorted_list[k])
position3  = 1
if position3 > max_ and position3 == len(temp):
for i in range(len(temp)):
unsorted_list[min_] = temp[i]
min_  = 1
``````

0条回复