# Merge Sort and Linked List Operations

9 Pages1107 Words290 Views
|
|
|
arr= [1, 12,100, 9, 5,7,6,8]crr= [3, 7, 15, 19, 20]brr= [2, 12, 15, 20, 45]drr= [2,5,8,10,16,77]err= [1, 3,14, 19, 45, 66]# making merge functiondef merge(a, b, m, n):c=[]i=0j=0#print("Sorting:")#print(a)#print(b)#print(m)#print(n)#print("while loop")while(i<m and j<n):#print(i)#print(a)#print(j)#print(b)if(a[i]<b[j]):c.append(a[i])i+=1else :c.append(b[j])
j+=1if (i>(m-1)):for x in range(j, len(b)):c.append(b[x])if (j>(n-1)):for x in range(i, len(a)):c.append(a[x])#print("Return sorted: " ,c)return c#print (merge(brr, crr, len(brr), len(crr)) )#print (merge(drr, err, len(drr), len(err)) )def mergeSort(a, st, lt):mid = int((st+lt)/2)#print(st,lt,mid)if (st ==mid):return aelse :left= a[st:mid]right= a[mid:lt]return merge(mergeSort(left, 0, len(left)), mergeSort(right, 0, len(right)), len(left), len(right))print(mergeSort(arr, 0, len(arr)))
class Node(object): def __init__(self, value): self.value=value self.next=None self.prev=Noneclass List(object): def __init__(self): self.head=None self.tail=None def insert(self,n,x): #Not actually perfect: how do we prepend to an existing list? if n!=None: x.next=n.next n.next=x x.prev=n if x.next!=None: x.next.prev=x if self.head==None: self.head=self.tail=x x.prev=x.next=None elif self.tail==n: self.tail=x def remove(self, val): """Remove a node from the list.""" current = self.head

## End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents

### Support

#### +1 306 205-2269

Chat with our experts. we are online and ready to help.