[Tutor] weird error in my python program : merge sort : resolved

Abhishek Pratap abhishek.vit at gmail.com
Thu Mar 22 21:54:24 CET 2012


I was not updating the list from the recursive call.

>     merge_sort(left,'left')
>     merge_sort(right,'right')

left = merge_sort(left,'left')
right = merge_sort(right,'right')


-A

-Abhi

On Thu, Mar 22, 2012 at 1:40 PM, Abhishek Pratap <abhishek.vit at gmail.com> wrote:
> I am imlpementing a merge sort algo for clarity purposes but my
> program is giving me weird answers. Sometimes it is able to sort and
> other times it does funky things. Help appreciated
>
>
> from random import *
> from numpy import *
>
> nums = [random.randint(100) for num in range(4)]
> #nums = [3,7,2,10]
>
> def merge_sort(nums, message='None'):
>     #print "%s : num of elements in the list %d" % (message,len(nums))
>     print '[merge_sort] %s : %s' % ( message, nums)
>
>     if len(nums) <= 1:
>         return nums
>
>     middle = len(nums)/2
>     print '[merge_sort] Mid point is %d' % middle
>     left  = nums[:middle]
>     right = nums[middle:]
>
>     merge_sort(left,'left')
>     merge_sort(right,'right')
>     print '[merge_sort] Calling merge on left: %s right : %s' % (left,right)
>     result = merge(left,right)
>     print '[merge_sort] %s' % result
>     return result
>
>
> def merge(left,right):
>     result = []
>     i,j = 0,0
>
>     print '[merge] left %s, right %s' % (left, right)
>
>     while i < len(left) and j < len(right):
>         print '[merge]Comparing left %d to right %d' % (left[i],right[j])
>         if left[i] <= right[j]:
>             result.append(left[i])
>             i += 1
>         else:
>             result.append(right[j])
>             j += 1
>
>         print '[merge]pushing to result',result
>
>     result.extend(left[i:])
>     result.extend(right[j:])
>     print '[merge] return',result
>     return result
>
>
> merge_sort(nums,'start')


More information about the Tutor mailing list