Below is the most compact merge sort function that I can come up with in Python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# Merge sort in python def mergesort(arr): # base case if len(arr) <=1: return arr # devide and conquer arr1 = mergesort(arr[0:len(arr)/2]) arr2 = mergesort(arr[len(arr)/2:]) # combine stage pointer1 = 0 pointer2 = 0 out_arr = [] while (pointer1<len(arr1)) and (pointer2<len(arr2)): if arr1[pointer1]<arr2[pointer2]: out_arr.append(arr1[pointer1]) pointer1 += 1 else: out_arr.append(arr2[pointer2]) pointer2 += 1 out_arr += arr1[pointer1:] + arr2[pointer2:] return out_arr |

And the following are the unit tests for it

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# unit testing mergesort tests = 100 maxlength = 100 from random import randrange, random for i in range(0, tests): tmp = [random() for j in range(0, randrange(0,maxlength))] print tmp a = tmp[:] b = tmp[:] print a print b c = mergesort(a) d = sorted(b) if c != d: print "b: ", d print "a: ", c raise ValueError('test failed '+ tmp) a = [i for i in range(11,1,-1)] print a print mergesort(a) print mergesort([1,2]) print mergesort([]) print mergesort([6,5,4,3,3,3,1]) print mergesort([4, 65, 2, -31, 0, 99, 99, 83, 782, 1]) |