Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Merge sort algorithm.
# Despues de revisar https://binary-coffee.dev/post/conociendo-el-ordenamiento-por-mezcla-merge-sort
# me animé a implementarlo en Python.
def MergeTwoOrderedLists(A, B):
"""
Merge two ordered lists.
:param A: a ordered collection with heterogeneous
comparable items with items in collection B
:param B: a ordered collection with heterogeneous
comparable items with items in collection A
:return: an array with all items in A and B ordered
Examples:
>>> MergeTwoOrderedLists([2, 4, 7], [1, 3, 5, 6])
[1, 2, 3, 4, 5, 6, 7]
>>> MergeTwoOrderedLists([], [1])
[1]
>>> MergeTwoOrderedLists([2], [1])
[1, 2]
"""
i = j = 0
total = len(A) + len(B)
result = []
while len(result) < total:
if i == len(A):
result.append(B[j])
j += 1
elif j == len(B):
result.append(A[i])
i += 1
elif i < len(A) and j < len(B) and A[i] < B[j]:
result.append(A[i])
i += 1
elif j < len(B):
result.append(B[j])
j += 1
return result
def MergeSort(A):
"""
Merge sort algorithm.
:param A: a collection with heterogeneous comparable items inside
:return: another collection ordered by ascending
Examples:
>>> MergeSort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> MergeSort([])
[]
>>> MergeSort([-2, -5, -45])
[-45, -5, -2]
"""
if len(A) < 2:
return list(A[: ])
middle = len(A) // 2
left = MergeSort(A[: middle])
right = MergeSort(A[middle: ])
result = MergeTwoOrderedLists(left, right)
return result
# Some tests:
assert MergeSort([]) == []
assert MergeSort(['A']) == ['A']
assert MergeSort(['B', 'A']) == ['A', 'B']
assert MergeSort([4,3,2,1]) == list(range(1, 5))
assert MergeSort([6, 2, 5, 1, 3, 4]) == list(range(1, 7))
a1000_501_1_500 = list(range(1000, 500, -1)) + list(range(1, 501))
assert MergeSort(a1000_501_1_500) == list(range(1, 1001))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment