I wrote a note for myself about merge sort.
--A high-speed sorting algorithm based on the divide-and-conquer method that can handle large data sizes. --Computational complexity is O (nlogn) --Because there are logn layers and the amount of calculation for each layer is O (n). --Stable sorting that does not change the order of the same values even if sorted --Requires memory to temporarily store data
marge_sort.py
def merge(A, left, mid, right):
L = []
for i in range(mid - left):
L.append(A[left + i])
L.append(1000) #Make sure the number is larger than the number to be sorted
R = []
for i in range(right - mid):
R.append(A[mid + i])
R.append(1000) #Make sure the number is larger than the number to be sorted
i = j = 0
for k in range(left, right):
if L[i] <= R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
j += 1
def merge_sort(A, left, right):
if left+1 < right:
mid = (left + right) // 2
merge_sort(A, left, mid)
merge_sort(A, mid, right)
merge(A, left, mid, right)
return A
print(merge_sort([3, 1, 10, 2.5, 11, 3, 21, 4, -1], 0, 9))
# [-1, 1, 2.5, 3, 3, 4, 10, 11, 21]
This time you can sort numbers less than 1000 in ascending order 1000 is set appropriately, so if you increase it, you can sort even larger numbers. I didn't make the total number of calls well ...
Merge sort in C language Sort algorithm and implementation in Python [Unity] I tried to visualize 12 sort algorithms
Recommended Posts