2. Merge sort

Merge sort

Approach

Divide

Divide the n-element sequence to be sorted

into two subsequences of n=2 elements each

Conquer

Sort the two subsequences recursively using merge sort.

Combine

Merge the two sorted subsequences to produce the sorted answer.

Merge

MERGE(A,p,q,r)

A - Array

p,q and r - indices into array

p <= q <= r

A[ p .. q ] , A[ q .. r ] --> A[ p .. r ]

(venv) [velmuruganponnusamy@localhost merge-sort]$ cat merge-sort.py

def merge(A,p,q,r):

# pre-requisities in python

# array slicing and index and length function

L1 = A[ p:q ]

L2 = A[ q:r ]

print("Array - {0} ".format(A))

print( "*" * 80 )

# try without this step and identify why are we performing append stats

# depends on the ascending and descending, 999999999 needs to be changed

# if asc -> positive high value

# if desc -> negative high value

L1.append(999999999)

L2.append(999999999)

i = 0

j = 0

for k in range(p,r):

if L1[i] <= L2[j]:

A[k] = L1[i]

i = i + 1

print(i,j,k)

print("Array - {0} ".format(A))

print( "*" * 80)

elif L1[i] > L2[j]:

A[k] = L2[j]

j = j + 1

print(i,j,k)

print("Array - {0} ".format(A))

print( "*" * 80 )

def merge_sort(A,p,r):

if p < r - 1:

q = int((p + r)/2) if r % 2 == 0 else int((p + r+1)/2)

# print(p,q,r)

# print(A)

merge_sort(A,p,q)

merge_sort(A,q,r)

merge(A,p,q,r)

A = [ 5,4,3,7,99,34,25 ]

print("Before sorting - " + str(A))

merge_sort(A,0,len(A))

print("After sorting - " + str(A))

(venv) [velmuruganponnusamy@localhost merge-sort]$ python3 merge-sort.py

Before sorting - [5, 4, 3, 7, 99, 34, 25]

Array - [5, 4, 3, 7, 99, 34, 25]

********************************************************************************

0 1 0

Array - [4, 4, 3, 7, 99, 34, 25]

********************************************************************************

1 1 1

Array - [4, 5, 3, 7, 99, 34, 25]

********************************************************************************

Array - [4, 5, 3, 7, 99, 34, 25]

********************************************************************************

1 0 2

Array - [4, 5, 3, 7, 99, 34, 25]

********************************************************************************

1 1 3

Array - [4, 5, 3, 7, 99, 34, 25]

********************************************************************************

Array - [4, 5, 3, 7, 99, 34, 25]

********************************************************************************

0 1 0

Array - [3, 5, 3, 7, 99, 34, 25]

********************************************************************************

1 1 1

Array - [3, 4, 3, 7, 99, 34, 25]

********************************************************************************

2 1 2

Array - [3, 4, 5, 7, 99, 34, 25]

********************************************************************************

2 2 3

Array - [3, 4, 5, 7, 99, 34, 25]

********************************************************************************

Array - [3, 4, 5, 7, 99, 34, 25]

********************************************************************************

0 1 4

Array - [3, 4, 5, 7, 34, 34, 25]

********************************************************************************

1 1 5

Array - [3, 4, 5, 7, 34, 99, 25]

********************************************************************************

Array - [3, 4, 5, 7, 34, 99, 25]

********************************************************************************

0 1 4

Array - [3, 4, 5, 7, 25, 99, 25]

********************************************************************************

1 1 5

Array - [3, 4, 5, 7, 25, 34, 25]

********************************************************************************

2 1 6