# 9 Recurrence relations and recursive algorithms¶

## Example 15:Page 421¶

In [2]:
print "MERGE SORT"
alist=[65,43,22,54,87,11,76,48,30,60,19,75,94,27,58,80]#List to be sorted
def mergesort(alist):
print "Splitting",alist
if len(alist)>1:

mid=len(alist)/2
left_half=alist[:mid]
right_half=alist[mid:]#Spltting into halves
mergesort(left_half)
mergesort(right_half)#Recirsive split to obtain values
i=0
j=0
k=0#Varaibles for indexing
while i<len(left_half) and j<len(right_half):
if left_half[i]<right_half[j]:
alist[k]=left_half[i]#Puts the minimum value in the beginning
i=i+1
else:
alist[k]=right_half[j]
j=j+1
k=k+1
while i<len(left_half):
alist[k]=left_half[i]#Combine left sorted elements to the whole list
i=i+1
k=k+1
while j<len(right_half):
alist[k]=right_half[j]#Combine right sorted elements to the wholw list
j=j+1
k=k+1
print "Merging",alist

mergesort(alist)
print(alist)

MERGE SORT
Splitting [65, 43, 22, 54, 87, 11, 76, 48, 30, 60, 19, 75, 94, 27, 58, 80]
Splitting [65, 43, 22, 54, 87, 11, 76, 48]
Splitting [65, 43, 22, 54]
Splitting [65, 43]
Splitting [65]
Merging [65]
Splitting [43]
Merging [43]
Merging [43, 65]
Splitting [22, 54]
Splitting [22]
Merging [22]
Splitting [54]
Merging [54]
Merging [22, 54]
Merging [22, 43, 54, 65]
Splitting [87, 11, 76, 48]
Splitting [87, 11]
Splitting [87]
Merging [87]
Splitting [11]
Merging [11]
Merging [11, 87]
Splitting [76, 48]
Splitting [76]
Merging [76]
Splitting [48]
Merging [48]
Merging [48, 76]
Merging [11, 48, 76, 87]
Merging [11, 22, 43, 48, 54, 65, 76, 87]
Splitting [30, 60, 19, 75, 94, 27, 58, 80]
Splitting [30, 60, 19, 75]
Splitting [30, 60]
Splitting [30]
Merging [30]
Splitting [60]
Merging [60]
Merging [30, 60]
Splitting [19, 75]
Splitting [19]
Merging [19]
Splitting [75]
Merging [75]
Merging [19, 75]
Merging [19, 30, 60, 75]
Splitting [94, 27, 58, 80]
Splitting [94, 27]
Splitting [94]
Merging [94]
Splitting [27]
Merging [27]
Merging [27, 94]
Splitting [58, 80]
Splitting [58]
Merging [58]
Splitting [80]
Merging [80]
Merging [58, 80]
Merging [27, 58, 80, 94]
Merging [19, 27, 30, 58, 60, 75, 80, 94]
Merging [11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]
[11, 19, 22, 27, 30, 43, 48, 54, 58, 60, 65, 75, 76, 80, 87, 94]


## Example 17:Page 424¶

In [3]:
print "BINARY SEARCH"
array=["" for i in range(100)]
temp=0#Variable checks if the element has been found. Initialised to zero, if it retains the same value till the end, then the element is not in the given list
n=input("Enter the number of elements")
print "Enter the elememts in sorted order"
for i in range(0,n):
array[i]=input()#Input the numbers in ascending order
item=input("Enter the item to be searched")
first=0#
last=n-1
while first<=last:
mid=(first+last)/2#Finds the middle element
if item==array[mid]:
print "Search is successfully completed"
temp=mid
print "The item is in position",temp+1

if item<array[mid]:#Divides the array into half depending on the value to be searched
last=mid-1
else:
first=mid+1
if temp==0:
print "Search is not successfully completed"


BINARY SEARCH
Enter the number of elements7
Enter the elememts in sorted order
9
16
25
49
50
67
84
Enter the item to be searched67
Search is successfully completed
The item is in position 6