Recursive Mergesort in Python

mergesort.py

def merge(left, right):
	if not len(left) or not len(right):
		return left or right

	result = []
	i, j = 0, 0
	while (len(result) < len(left) + len(right)):
		if left[i] < right[j]:
			result.append(left[i])
			i+= 1
		else:
			result.append(right[j])
			j+= 1
		if i == len(left) or j == len(right):
			result.extend(left[i:] or right[j:])
			break 

	return result

def mergesort(list):
	if len(list) < 2:
		return list

	middle = len(list)/2
	left = mergesort(list[:middle])
	right = mergesort(list[middle:])

	return merge(left, right)

if __name__ == "__main__":
	print mergesort([3,4,5,1,2,8,3,7,6])

Good sample for recursive merge. Thanks!

Far cleaner and easier to wrap my mind around than the version presented in my algorithms class. Thank you for helping me see it!

#!/usr/bin/python3

def merge(left, right, A):
	i, j, k = 0, 0, 0
	while i < len(left) and j < len(right):
		if left[i] <= right[j]: A[k], i, k = left[i], i + 1, k + 1
		else: A[k], j, k = right[j], j + 1, k + 1
	while i < len(left): A[k], i, k = left[i], i + 1, k + 1
	while j < len(right): A[k], j, k = right[j], j + 1, k + 1

def mergeSort(A):
	if len(A) < 2: return
	left, right = A[ : len(A) // 2], A[len(A) // 2 : ]
	mergeSort(left)
	mergeSort(right)
	merge(left, right, A)

def main():
	n = input()
	A = list(map(int, input().split()))
	mergeSort(A)
	print(' '.join(list(map(str, A))))
	
if __name__ == '__main__':
	main()

This is much cleaner

Nice and Simple . I made a small change on the same idea and got rid of the breaks .
`

class MergeSort(object):
    def __init__(self):
        super(MergeSort, self).__init__()

def mergeSort(self, arr):
    if (len(arr))<2:return arr
    mid = int((len(arr))/2)
    left,right =  self.mergeSort(arr[:mid]),self.mergeSort(arr[mid:])
    return self.merge(left,right)

def merge(self,l,r):
    if not l or not r:return l or r
    n1,n2,res,i,j = len(l),len(r),[],0,0 
    l.append(float('inf'))
    r.append(float('inf'))
    for k in range(n1+n2):
        if l[i]<=r[j]:
            res.append(l[i])
            i+=1
        else:
            res.append(r[j])
            j+=1
    return res

`

Thank you for this piece of code)
By the way, if someone find it interesting, here is merge realisation with deque from python collections:

from collections import deque
from itertools import islice


def merge(a, b):
    c = deque([])
    while a and b:
        i = a[0]
        j = b[0]
        if i <= j:
            c.append(i)
            a.popleft()
        else:
            c.append(j)
            b.popleft()
    if a:
        c.extend(a)
    if b:
        c.extend(b)
    return c


def merge_sort(A):
    if len(A) < 2:
        return A
    m = len(A) // 2
    l = merge_sort(deque(islice(A, 0, m)))
    r = merge_sort(deque(islice(A, m, len(A))))
    return merge(l, r)


if __name__ == '__main__':
    print(merge_sort([3, 4, 5, 1, 2, 8, 3, 7, 6]))

Here is merge sort in one function with detailed information on running process

def merge_sort(nlist):
    print("Splitting ", nlist)
    if len(nlist) > 1:
        mid = len(nlist) // 2
        lefthalf = nlist[:mid]
        righthalf = nlist[mid:]
        merge_sort(lefthalf)
        merge_sort(righthalf)
        i = j = k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                nlist[k] = lefthalf[i]
                i = i + 1
            else:
                nlist[k] = righthalf[j]
                j = j + 1
            k = k + 1

        while i < len(lefthalf):
            nlist[k] = lefthalf[i]
            i = i + 1
            k = k + 1

        while j < len(righthalf):
            nlist[k] = righthalf[j]
            j = j + 1
            k = k + 1
    print("Merging ", nlist)