#This program gives an example of Merge sort

# Merge sort is a divide and conquer algorithm. In the divide and

# conquer paradigm, a problem is broken into pieces where each piece

# still retains all the properties of the larger problem -- except

# its size. To solve the original problem, each piece is solved

# individually; then the pieces are merged back together.

# Best = Average = Worst = O(nlog(n))

def merge(a,b):

""" Function to merge two arrays """

c = []

while len(a) != 0 and len(b) != 0:

if a[0] < b[0]:

c.append(a[0])

a.remove(a[0])

else:

c.append(b[0])

b.remove(b[0])

if len(a) == 0:

c += b

else:

c += a

return c

# Code for merge sort

def mergeSort(x):

""" Function to sort an array using merge sort algorithm """

if len(x) == 0 or len(x) == 1:

return x

else:

middle = len(x)//2

a = mergeSort(x[:middle])

b = mergeSort(x[middle:])

return merge(a,b)

if __name__ == '__main__':

List = [3, 4, 2, 6, 5, 7, 1, 9]

print('Sorted List:',mergeSort(List))