Array data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]
Divide into left and right in the middle of the array => Left [3,1,9,4,2] Right [5,7,6,8,10] Middle: 5
Divide further by left and right (using recursion) => Left [3,1,9,4,2]-> Left [3,1] Right [9,4,2] Middle: 2 Right [5,7,6,8,10]-> Left [5,7] Right [6,8,10] ....
Finally, it will be [3], [1], [9], [4], [2], [5], [7], [6], [8], [10](preparation completed) !)
This time, the values divided into two are sorted in order from the left (because it starts from 0), and the sort result is assigned to result_sort (combination). [3,1], [4,2] => Each Sort [1,3] [2,4]
sample.py
data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]
Assign data to a variable
sample.py
def merge_sort(data):
if len(data) <= 1: #True if the contents of the array are 1 or less
return data
center = len(data) // 2 #Center of array
left = merge_sort(data[:center])#Divided to the left[3,1,9,4,2] => [3,1] => [3]
right = merge_sort(data[center:]) #Divided to the right[5,7,6,8,10] => [9,4,2] => [1]
return left, right #=> [3], [1]Is passed
You can do 1 ~ 3 with this code.
sample.py
def merge_sort(data):
if len(data) <= 1: #True if the contents of the array are 1 or less
return data
center = len(data) // 2 #Center of array
left = merge_sort(data[:center])#Divided to the left[3,1,9,4,2] => [3,1] => [3]
right = merge_sort(data[center:]) #Divided to the right[5,7,6,8,10] => [9,4,2] => [1]
return merge(left, right)
Just add return merge (left, right)
sample.py
def merge(left, right):
result_sort = [] #Combined result
left_i, right_j = 0, 0
print(left + right) #=>You can see the array you are trying to sort
while(left_i < len(left)) and (right_j < len(right)):
if left[left_i] <= right[right_j]:
result_sort.append(left[left_i]) #Here, compare the right and left you are trying to combine and hit the result.
left_i += 1
else:
result_sort.append(right[right_j]) #Here, compare the right and left you are trying to combine and hit the result.
right_j += 1
if len(left[left_i:]) != 0: #=>True if the number in the left array that has been sorted but left over is not 0(left_Check with i)
result_sort.extend(left[left_i:])
if len(right[right_j:]) != 0:
result_sort.extend(right[right_j:]) #True (right) if the number in the array of right that has been sorted but is left over is not 0_Confirm with j)
print(result_sort) #=>You can see the sorted array
return result #Final return value
Doing 4 ~ 8