Commit 9e366c9
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,41 @@ | |||
| 1 | + #This program gives an example of Merge sort | ||
| 2 | + | ||
| 3 | + # Merge sort is a divide and conquer algorithm. In the divide and | ||
| 4 | + # conquer paradigm, a problem is broken into pieces where each piece | ||
| 5 | + # still retains all the properties of the larger problem -- except | ||
| 6 | + # its size. To solve the original problem, each piece is solved | ||
| 7 | + # individually; then the pieces are merged back together. | ||
| 8 | + | ||
| 9 | + # Best = Average = Worst = O(nlog(n)) | ||
| 10 | + | ||
| 11 | + def merge(a,b): | ||
| 12 | + """ Function to merge two arrays """ | ||
| 13 | + c = [] | ||
| 14 | + while len(a) != 0 and len(b) != 0: | ||
| 15 | + if a[0] < b[0]: | ||
| 16 | + c.append(a[0]) | ||
| 17 | + a.remove(a[0]) | ||
| 18 | + else: | ||
| 19 | + c.append(b[0]) | ||
| 20 | + b.remove(b[0]) | ||
| 21 | + if len(a) == 0: | ||
| 22 | + c += b | ||
| 23 | + else: | ||
| 24 | + c += a | ||
| 25 | + return c | ||
| 26 | + | ||
| 27 | + # Code for merge sort | ||
| 28 | + | ||
| 29 | + def mergeSort(x): | ||
| 30 | + """ Function to sort an array using merge sort algorithm """ | ||
| 31 | + if len(x) == 0 or len(x) == 1: | ||
| 32 | + return x | ||
| 33 | + else: | ||
| 34 | + middle = len(x)//2 | ||
| 35 | + a = mergeSort(x[:middle]) | ||
| 36 | + b = mergeSort(x[middle:]) | ||
| 37 | + return merge(a,b) | ||
| 38 | + | ||
| 39 | + if __name__ == '__main__': | ||
| 40 | + List = [3, 4, 2, 6, 5, 7, 1, 9] | ||
| 41 | + print('Sorted List:',mergeSort(List)) | ||
0 commit comments