با سلام
این سورس برای زمانی عمل میکنه که دو قسمت کرده باشیم.
import random, time
def merge(A, B):
"""
Returns a new list C that contains all the elements of A and B
in sorted order.
A and B must be in sorted order for this to work!
>>> A = [3, 5, 6, 7, 32, 235]
>>> B = [-1, 4, 5, 6, 7, 8, 9, 19, 65]
>>> merge(A, B)
[-1, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9, 19, 32, 65, 235]
"""
n = len(A) + len(B)
result = []
a, b = 0, 0
for c in range(n): # c is incremented each iteration
if a == len(A): # A is done
result.append(B[b])
b += 1
elif b == len(B): # B is done
result.append(A[a])
a += 1
elif A[a] < B[b]: # elements on both A and B
result.append(A[a])
a += 1
else:
result.append(B[b])
b += 1
return result
def mergesort(lst):
"""
Performs mergesort on lst. Returns a new list that is in sorted
order. The passed-in lst is not modified.
Note: This is not the most efficient version of mergesort. Far
from it, in fact. It is written to be easy to understand. The
slicing to create the left and right lists is inefficient, and
should be replaced with in-place operations if you need it to
run faster.
"""
n = len(lst)
if n < 2: # nothing to sort!
return lst[:] # so just return a copy and quit
else:
mid = n / 2 # split the list
left = lst[:mid] # into two equal
right = lst[mid:] # halves
sorted_left = mergesort(left) # recursively sort
sorted_right = mergesort(right) # each half
return merge(sorted_left, sorted_right)
# bubble sort included for comparison
def bubble_up_once(lst):
i = 1
while i < len(lst):
if lst[i-1] > lst[i]:
lst[i-1], lst[i] = lst[i], lst[i-1] # swap
i += 1
def bubble_sort(lst):
for x in lst:
bubble_up_once(lst)
if __name__ == '__main__':
lst = range(10000)
random.shuffle(lst)
result = mergesort(lst)
ببینید حالتی در نظر بگیرید که 4 تا لیست دارید و میخواهید مرتب کنید.با دنبال کردن روند بالا برای 4 قسمتی در نظر بگیرید.اگه مشکلی بود بپرسید.
