import math
def merge(a, aux, lo, mid, hi):
assert isSorted(a, lo, mid)
assert isSorted(a, mid+1, hi)
for k in range(lo, hi+1):
aux[k] = a[k]
i, j = lo, mid + 1
for k in range(lo, hi+1):
if i > mid:
a[k] = aux[j]
j += 1
elif j > hi:
a[k] = aux[i]
i += 1
elif aux[i] < aux[j]:
a[k] = aux[i]
i += 1
else:
a[k] = aux[j]
j += 1
assert isSorted(a, lo, hi)
def sort(a, aux, lo, hi):
if (lo >= hi): return a
mid = math.floor(lo + (hi-lo) / 2)
sort(a, aux, lo, mid)
sort(a, aux, mid+1, hi)
merge(a, aux, lo, mid, hi)
def merge_sort(a):
aux = [0] * len(a)
sort(a, aux, 0, len(a)-1)
assert isSortedArray(a)
def isSorted(a, lo, hi):
for i in range(lo, hi-1):
if a[i+1] < a[i]:
return False
return True
def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True
def main():
arr = [3, 7, 2, 8, 14, 20, 5, 19, 10, 17, 1, 16, 11, 18, 12, 9, 13, 4, 15, 6]
#arr = [3, 2, 5, 1, 4]
merge_sort(arr)
print(arr)
if __name__ == "__main__":
main()
aW1wb3J0IG1hdGgKCmRlZiBtZXJnZShhLCBhdXgsIGxvLCBtaWQsIGhpKToKICAgIGFzc2VydCBpc1NvcnRlZChhLCBsbywgbWlkKQogICAgYXNzZXJ0IGlzU29ydGVkKGEsIG1pZCsxLCBoaSkKCiAgICBmb3IgayBpbiByYW5nZShsbywgaGkrMSk6CiAgICAgICAgYXV4W2tdID0gYVtrXQoKICAgIGksIGogPSBsbywgbWlkICsgMQogICAgZm9yIGsgaW4gcmFuZ2UobG8sIGhpKzEpOgogICAgICAgIGlmIGkgPiBtaWQ6CiAgICAgICAgICAgIGFba10gPSBhdXhbal0KICAgICAgICAgICAgaiArPSAxCiAgICAgICAgZWxpZiBqID4gaGk6CiAgICAgICAgICAgIGFba10gPSBhdXhbaV0KICAgICAgICAgICAgaSArPSAxCiAgICAgICAgZWxpZiBhdXhbaV0gPCBhdXhbal06CiAgICAgICAgICAgIGFba10gPSBhdXhbaV0KICAgICAgICAgICAgaSArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgYVtrXSA9IGF1eFtqXQogICAgICAgICAgICBqICs9IDEKICAgIGFzc2VydCBpc1NvcnRlZChhLCBsbywgaGkpCgoKZGVmIHNvcnQoYSwgYXV4LCBsbywgaGkpOgogICAgaWYgKGxvID49IGhpKTogcmV0dXJuIGEKICAgIG1pZCA9IG1hdGguZmxvb3IobG8gKyAoaGktbG8pIC8gMikKICAgIAogICAgc29ydChhLCBhdXgsIGxvLCBtaWQpCiAgICBzb3J0KGEsIGF1eCwgbWlkKzEsIGhpKQogICAgbWVyZ2UoYSwgYXV4LCBsbywgbWlkLCBoaSkKCmRlZiBtZXJnZV9zb3J0KGEpOgogICAgYXV4ID0gWzBdICogbGVuKGEpCiAgICBzb3J0KGEsIGF1eCwgMCwgbGVuKGEpLTEpCiAgICBhc3NlcnQgaXNTb3J0ZWRBcnJheShhKQoKZGVmIGlzU29ydGVkKGEsIGxvLCBoaSk6CiAgICBmb3IgaSBpbiByYW5nZShsbywgaGktMSk6CiAgICAgICAgaWYgYVtpKzFdIDwgYVtpXToKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCiAgICByZXR1cm4gVHJ1ZQoKZGVmIGlzU29ydGVkQXJyYXkoYSk6CiAgICBmb3IgaSBpbiByYW5nZSgwLCBsZW4oYSktMSk6CiAgICAgICAgaWYgYVtpKzFdIDwgYVtpXToKICAgICAgICAgICAgcmV0dXJuIEZhbHNlCiAgICByZXR1cm4gVHJ1ZQoKZGVmIG1haW4oKToKICAgIGFyciA9IFszLCA3LCAyLCA4LCAxNCwgMjAsIDUsIDE5LCAxMCwgMTcsIDEsIDE2LCAxMSwgMTgsIDEyLCA5LCAxMywgNCwgMTUsIDZdCiAgICAjYXJyID0gWzMsIDIsIDUsIDEsIDRdCiAgICBtZXJnZV9zb3J0KGFycikKICAgIHByaW50KGFycikKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBtYWluKCk=