On May 30, 2:48 pm, [email protected] wrote:
> Code :
> -----
> def mergeSort(alist):
> print("Splitting ",alist)
> if len(alist)>1:
> mid = len(alist)//2
> lefthalf = alist[:mid]
> righthalf = alist[mid:]
>
> mergeSort(lefthalf)
> mergeSort(righthalf)
>
> i=0
> j=0
> k=0
> while i<len(lefthalf) and j<len(righthalf):
> if lefthalf[i]<righthalf[j]:
> alist[k]=lefthalf[i]
> i=i+1
> else:
> alist[k]=righthalf[j]
> j=j+1
> k=k+1
>
> while i<len(lefthalf):
> alist[k]=lefthalf[i]
> i=i+1
> k=k+1
>
> while j<len(righthalf):
> alist[k]=righthalf[j]
> j=j+1
> k=k+1
> print("Merging ",alist)
>
> alist = [54,26,93,17,77,31,44,55,20]
> mergeSort(alist)
> print(alist)
>
> Output:
> -------
> ('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
> ('Splitting ', [54, 26, 93, 17])
> ('Splitting ', [54, 26])
> ('Splitting ', [54])
> ('Merging ', [54])
> ('Splitting ', [26])
> ('Merging ', [26])
> ('Merging ', [26, 54])
> ('Splitting ', [93, 17])
> ('Splitting ', [93])
> ('Merging ', [93])
> ('Splitting ', [17])
> ('Merging ', [17])
> ('Merging ', [17, 93])
> ('Merging ', [17, 26, 54, 93])
> ('Splitting ', [77, 31, 44, 55, 20])
> ('Splitting ', [77, 31])
> ('Splitting ', [77])
> ('Merging ', [77])
> ('Splitting ', [31])
> ('Merging ', [31])
> ('Merging ', [31, 77])
> ('Splitting ', [44, 55, 20])
> ('Splitting ', [44])
> ('Merging ', [44])
> ('Splitting ', [55, 20])
> ('Splitting ', [55])
> ('Merging ', [55])
> ('Splitting ', [20])
> ('Merging ', [20])
> ('Merging ', [20, 55])
> ('Merging ', [20, 44, 55])
> ('Merging ', [20, 31, 44, 55, 77])
> ('Merging ', [17, 20, 26, 31, 44, 54, 55, 77, 93])
> [17, 20, 26, 31, 44, 54, 55, 77, 93]
>
> Question:
> ---------
> Function mergeSort is called only once, but it is getting recursively
> executed after the printing the last statement "print("Merging ",alist)". But
> don't recursion taking place except at these places "mergeSort(lefthalf),
> mergeSort(righthalf)"
>
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure
> how.
>
> Can anyone please help me out here?
Not in direct answer to your question... Still see if this helps you
to understand mergesorting better.
I generally find that mixing recursion along with imperative
programming makes recursion look difficult.
Imperative programming goes scot-free and recursion gets a bad name!!
So here is a pure recursive/functional solution. Tell me if you
understand it better (or worse!!)
Its written to demonstrate the IDEA of mergesort. Its actual
efficiency is sub-par for various reasons.
-------------------------------------
# merging two lists, both assumed sorted
def merge(a,b):
if a == []: return b
elif b== []: return a
elif a[0] < b[0]:
return [a[0]] + merge(a[1:],b)
else:
return [b[0]] + merge(a,b[1:])
# The same as merge above written in pure functional style
def merge1(a,b):
return (b if a == [] else
a if b == [] else
[a[0]] + merge(a[1:],b) if a[0] < b[0] else
[b[0]] + merge(a,b[1:])
)
def mergeSort(alist):
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
return merge1(mergeSort(lefthalf),mergeSort(righthalf) )
else:
return alist
--
http://mail.python.org/mailman/listinfo/python-list
