seeditsolution · seeditsolution · Oct 2, 2020 · Oct 2, 2020
diff --git a/mergesort b/mergesort
@@ -0,0 +1,41 @@
+#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))