def merge( a, left, middle, right) :
"""
middle-- последний элемент первой части
"""
tmp = [ 0 ] * ( right + 1 - left)
pos1 = left
pos2 = middle + 1
pos3 = 0
while pos1 <= middle and pos2 <= right:
if a[ pos1] <= a[ pos2] :
tmp[ pos3] = a[ pos1]
pos1 += 1
else :
tmp[ pos3] = a[ pos2]
pos2 += 1
pos3 += 1
while pos1 <= middle:
tmp[ pos3] = a[ pos1]
pos1 += 1
pos3 += 1
while pos2 <= right:
tmp[ pos3] = a[ pos2]
pos2 += 1
pos3 += 1
for i in range ( pos3) :
a[ left + i] = tmp[ i]
def merge_sort( a, left= 0 , right= None ) :
# 1
# if right == -228:
# right = len(a) - 1
# 2
right = right or ( len ( a) - 1 )
if left < right:
middle = ( left + right) // 2
merge_sort( a, left, middle)
merge_sort( a, middle + 1 , right)
merge( a, left, middle, right)
A = [ 4 , 2 , 5 , 1 , 3 ]
A_sorted = [ 1 , 2 , 3 , 4 , 5 ]
merge_sort( A)
print ( A)
ZGVmIG1lcmdlKGEsIGxlZnQsIG1pZGRsZSwgcmlnaHQpOgogICAgIiIiCiAgICBtaWRkbGUtLSDQv9C+0YHQu9C10LTQvdC40Lkg0Y3Qu9C10LzQtdC90YIg0L/QtdGA0LLQvtC5INGH0LDRgdGC0LgKICAgICIiIgogICAgdG1wID0gWzBdICogKHJpZ2h0ICsgMSAtIGxlZnQpCiAgICBwb3MxID0gbGVmdAogICAgcG9zMiA9IG1pZGRsZSArIDEKICAgIHBvczMgPSAwCiAgICB3aGlsZSBwb3MxIDw9IG1pZGRsZSBhbmQgcG9zMiA8PSByaWdodDoKICAgICAgICBpZiBhW3BvczFdIDw9IGFbcG9zMl06CiAgICAgICAgICAgIHRtcFtwb3MzXSA9IGFbcG9zMV0KICAgICAgICAgICAgcG9zMSArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgdG1wW3BvczNdID0gYVtwb3MyXQogICAgICAgICAgICBwb3MyICs9IDEKICAgICAgICBwb3MzICs9IDEKICAgIHdoaWxlIHBvczEgPD0gbWlkZGxlOgogICAgICAgIHRtcFtwb3MzXSA9IGFbcG9zMV0KICAgICAgICBwb3MxICs9IDEKICAgICAgICBwb3MzICs9IDEKICAgIHdoaWxlIHBvczIgPD0gcmlnaHQ6CiAgICAgICAgdG1wW3BvczNdID0gYVtwb3MyXQogICAgICAgIHBvczIgKz0gMQogICAgICAgIHBvczMgKz0gMQogICAgZm9yIGkgaW4gcmFuZ2UocG9zMyk6CiAgICAgICAgYVtsZWZ0ICsgaV0gPSB0bXBbaV0KCgpkZWYgbWVyZ2Vfc29ydChhLCBsZWZ0PTAsIHJpZ2h0PU5vbmUpOgogICAgIyAxCiAgICAjIGlmIHJpZ2h0ID09IC0yMjg6CiAgICAjICAgIHJpZ2h0ID0gbGVuKGEpIC0gMQogICAgIyAyCiAgICByaWdodCA9IHJpZ2h0IG9yIChsZW4oYSkgLSAxKQoKICAgIGlmIGxlZnQgPCByaWdodDoKICAgICAgICBtaWRkbGUgPSAobGVmdCArIHJpZ2h0KSAvLyAyCiAgICAgICAgbWVyZ2Vfc29ydChhLCBsZWZ0LCBtaWRkbGUpCiAgICAgICAgbWVyZ2Vfc29ydChhLCBtaWRkbGUgKyAxLCByaWdodCkKICAgICAgICBtZXJnZShhLCBsZWZ0LCBtaWRkbGUsIHJpZ2h0KQogICAgICAgIAoKQSA9IFs0LCAyLCA1LCAxLCAzXQpBX3NvcnRlZCA9IFsxLCAyLCAzLCA0LCA1XQptZXJnZV9zb3J0KEEpCnByaW50KEEp
stdout
stderr
Traceback (most recent call last):
File "./prog.py", line 45, in <module>
File "./prog.py", line 38, in merge_sort
File "./prog.py", line 38, in merge_sort
File "./prog.py", line 38, in merge_sort
[Previous line repeated 995 more times]
File "./prog.py", line 36, in merge_sort
RecursionError: maximum recursion depth exceeded in comparison