Python Merge Sort change Psuedocode to Python code Merge Sor

[Python] [Merge Sort] change Psuedocode to Python code

Merge Sort MERGE(A, p, q, r) n1 = q - p + 1//length of the first sublist n2 = r - q//length of the second sublist let L[1..n1 + 1] and R[1..n2 + 1] be new arrays for i = 1 to n1 L[i] = A[p + i - 1]//copy A[1..q] to L for j = 1 to n2 R[j] = A[q + j]//copy A[q+1., r] to R L [n1 + 1] = Infinity//a sentinel marking the end of R[n2 + 1] = Infinity//a sentinel marking the end of sequence i = 1 j = 1 for k = p to r//select the smaller of the two 13 if L[i]

Solution

Following is the python code for the same:

def merge( A, p, q, r ):
   n1 = q - p + 1;       #length of the first sublist
   n2 = r - q;           #length of the second sublist
   #make two new arrays
   L = [0]*(n1+ 1);
   R = [0]*(n2+ 1 );
   for i in range(n1):
       L[i] = A[ p + i ];
   for j in range(n2):
       R[j] = A[ q + j + 1 ];
   L[ n1 ] = 100000000;
   R[ n2 ] = 100000000;
   i = 0;
   j = 0;
   for l in range(r-p+1):
       k = l + p;
       if L[i] <= R[j]:
           A[k] = L[i];
           i = i + 1;
       else:
           A[k] = R[j];
           j = j + 1;

def merge_sort( A , p , r ):
   if p < r:
       q = (p + r)/2;
       merge_sort( A, p, q );
       merge_sort( A, q+1, r );
       merge( A, p , q, r );

A = [4,3,4,23,1,2,33,4];
print A;
merge_sort( A, 0, len(A)-1 );
print A;

A = [34,12,321, 11,23 , 11 , 1, 2 ,3,4,5,55,532, 23];
print A;
merge_sort( A, 0, len(A)-1 );
print A;

A = [12,212,33, 44, 41, 3, 2, 1 ,122];
print A;
merge_sort( A, 0, len(A)-1 );
print A;