Questions based on merge sort , insertion sort and heap sort

Merge Sort, Heap Sort , RSA and Convex

Video referred for merge sort <https://www.youtube.com/watch?v=jeaxzxErLKk>

def mergeSort(alist):
2	    print("Splitting ",alist)
3	    if len(alist)>1:
4	        mid = len(alist)//2
5	        lefthalf = alist[:mid]
6	        righthalf = alist[mid:]
7	
8	        mergeSort(lefthalf)
9	        mergeSort(righthalf)
10	
11	        i=0
12	        j=0
13	        k=0
14	        while i<len(lefthalf) and j<len(righthalf):
15	            if lefthalf[i]<righthalf[j]:
16	                alist[k]=lefthalf[i]
17	                i=i+1
18	            else:
19	                alist[k]=righthalf[j]
20	                j=j+1
21	            k=k+1
22	
23	        while i<len(lefthalf):
24	            alist[k]=lefthalf[i]
25	            i=i+1
26	            k=k+1
27	
28	        while j<len(righthalf):
29	            alist[k]=righthalf[j]
30	            j=j+1
31	            k=k+1
32	    print("Merging ",alist)
33	
34	alist = [54,26,93,17,77,31,44,55,20]
35	mergeSort(alist)
36	print(alist)

Use the python visualization technique to fully understand how it is working and how it will be implemented on code. <http://www.pythontutor.com/visualize.html#mode=display>

If you are using python visualization then you can see how to allocate memory and deallocate it once the work is done. 

<Video also describes how we have come to O(nlogn) complexity> 


2- Convex Hull Graham's Scan Algorithm 

<https://www.youtube.com/watch?v=QYrpHE8iDGg> referred to this video for the definition of Graham Scan Algorithm
<https://www.youtube.com/watch?v=5D9F1HA6-f4> for more elaborate definition 

3- RSA Cryptography 

<https://www.youtube.com/watch?v=kYasb426Yjk> simple example very beautifully explained

4- Heap Sort 

<https://www.youtube.com/watch?v=B7hVxCmfPtM> the video is extremely helpful :)

It is nearly complete binary tree 
root of the tree is the first element 
parent(i) = i/2
left(i) = 2i   <This is the advantage of having complete binary tree>
right(i) = 2i + 1
max heap and min heap are two types of 
max heap - key of the node is always greater than the keys of the its children. It is recursive
min heap has similar properties
build_maxheap - produces a maxheap from an unordered array
max_heapify (A,i)- correct a single violation of the heap property in a subtree's root.
(Here you have to assume that the trees rooted at left(i) and right(i) are max heaps)
complexity of max_heapify is O(logn)

Convert A[1....n] into a max_heap 
Build_max_heap(A):
for i = n/2 downto 1 :
do max heapify(A,i)

elements A[n/2 + 1.....n] are all leaves 
<do look at this links http://stackoverflow.com/questions/9755721/build-heap-complexity>