Merge Sort Implementation in Python
Today I post the python implementation of merge sort. This is straight-forward implementation of the algorithm presented in the book Introduction to Algorithms [CLRS]. If you think the implementation can be more Pythonic, feel free to comment.
Here is my code:
Here is my code:
def merge(li, start, mid, end):
left_li = []
left_li.extend(li[start : mid+1])
right_li = []
right_li.extend(li[mid+1: end+1])
left_li.append(2147483647)
right_li.append(2147483647)
i = 0
j = 0
for k in range(start, end+1):
if left_li[i] <= right_li[j]:
li[k] = left_li[i]
i += 1
else:
li[k] = right_li[j]
j += 1
def merge_sort(li, start, end):
if start < end:
mid = (start + end) / 2
merge_sort(li, start, mid)
merge_sort(li, mid+1, end)
merge(li, start, mid, end)
if __name__ == "__main__":
li = [5, 2, 4, 7, 1, 3, 2, 6, -4]
print li
merge_sort(li, 0, len(li)-1)
print li
You can test the merge sort implementation against this problem: http://www.spoj.com/problems/MERGSORT/
Comments
def merge_sort(series):
iseries = [[i] for i in series]
while len(iseries) > 1:
iseries = [merge(a,b) if b else a for a,b in map(None,*[iter(iseries)]*2) ]
return iseries[0]
def merge(A, B):
return(
[(A if A[0]>B[0] else B).pop(0) for i in A+B if len(A) and len(B)>0]
+ A + B
)
print merge_sort([1,2,3,91,22,42,11,4,5,6])