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])

Your work is impressive.
It is very clear and easy to understand the logic behind it!

this doesn't work in my python, 3.4.4
you suck dude

@bobfshcake because py2 divides integers diffirently, for py3 add integer conversion on line 24:

middle = int(len(list)/2)

also print functions are not compatible among py2 and py3 , add brackets in print call on line 31:

print( mergesort([3,4,5,1,2,8,3,7,6]) )

what's use of line 2 and 3? It seems to work without those. Also, 'break' in the last 'if' case of 'while' loop.
Thank you!!

Very nice code, I like it!

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)