#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))