1def merge_sort(arr):
2 # The last array split
3 if len(arr) <= 1:
4 return arr
5 mid = len(arr) // 2
6 # Perform merge_sort recursively on both halves
7 left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
8
9 # Merge each side together
10 return merge(left, right, arr.copy())
11
12
13def merge(left, right, merged):
14
15 left_cursor, right_cursor = 0, 0
16 while left_cursor < len(left) and right_cursor < len(right):
17
18 # Sort each one and place into the result
19 if left[left_cursor] <= right[right_cursor]:
20 merged[left_cursor+right_cursor]=left[left_cursor]
21 left_cursor += 1
22 else:
23 merged[left_cursor + right_cursor] = right[right_cursor]
24 right_cursor += 1
25
26 for left_cursor in range(left_cursor, len(left)):
27 merged[left_cursor + right_cursor] = left[left_cursor]
28
29 for right_cursor in range(right_cursor, len(right)):
30 merged[left_cursor + right_cursor] = right[right_cursor]
31
32 return merged
1def mergeSort(myList):
2 if len(myList) > 1:
3 mid = len(myList) // 2
4 left = myList[:mid]
5 right = myList[mid:]
6
7 # Recursive call on each half
8 mergeSort(left)
9 mergeSort(right)
10
11 # Two iterators for traversing the two halves
12 i = 0
13 j = 0
14
15 # Iterator for the main list
16 k = 0
17
18 while i < len(left) and j < len(right):
19 if left[i] < right[j]:
20 # The value from the left half has been used
21 myList[k] = left[i]
22 # Move the iterator forward
23 i += 1
24 else:
25 myList[k] = right[j]
26 j += 1
27 # Move to the next slot
28 k += 1
29
30 # For all the remaining values
31 while i < len(left):
32 myList[k] = left[i]
33 i += 1
34 k += 1
35
36 while j < len(right):
37 myList[k]=right[j]
38 j += 1
39 k += 1
40
41myList = [54,26,93,17,77,31,44,55,20]
42mergeSort(myList)
43print(myList)
1def mergesort(list1):
2 if len(list1) >1 :
3
4 mid = len(list1)//2
5 left_list = list1[:mid]
6 right_list = list1[mid:]
7 mergesort(left_list) #Using recursion down here for the sub list
8 mergesort(right_list) #Using recursion down here for the sub list
9 i = 0
10 j = 0
11 k = 0
12 while i<len(left_list) and j<len(right_list):
13 if left_list[i]< right_list[j]:
14 list1[k] = left_list[i]
15 i+=1
16 k+=1
17 else:
18 list1[k] = right_list[j]
19 j+=1
20 k+=1
21 while i < len(left_list): # I did this as for the end condition of above loop as when i or j will be equal to len(left/right list)
22 list1[k] = left_list[i]
23 i+=1
24 k+=1
25
26 while j < len(right_list):
27 list1[k] = right_list[j]
28 j+=1
29 k+=1
30#Start watching from here and then as when function call will come then go check function
31n = int(input("Enter how many element you want in the list : "))
32list1 = [int(input()) for i in range(n)]
33mergesort(list1)
34print("sorted list : " + str(list1))
1def mergeSort(arr):
2
3 if len(arr) > 1:
4
5 a = len(arr)//2
6
7 l = arr[:a]
8
9 r = arr[a:]
10
11 # Sort the two halves
12
13 mergeSort(l)
14
15 mergeSort(r)
16
17 b = c = d = 0
18
19 while b < len(l) and c < len(r):
20
21 if l[b] < r[c]:
22
23 arr[d] = l[b]
24
25 b += 1
26
27 else:
28
29 arr[d] = r[c]
30
31 c += 1
32
33 d += 1
34
35 while b < len(l):
36
37 arr[d] = l[b]
38
39 b += 1
40
41 d += 1
42
43 while c < len(r):
44
45 arr[d] = r[c]
46
47 c += 1
48
49 d += 1
50
51
52def printList(arr):
53
54 for i in range(len(arr)):
55
56 print(arr[i], end=" ")
57
58 print()
59
60
61# Driver program
62
63if __name__ == '__main__':
64
65 arr = [0,1,3,5,7,9,2,4,6,8]
66
67 mergeSort(arr)
68
69 print("Sorted array is: ")
70
71 printList(arr)
72
73
74
1def mergeSort(arr):
2 if len(arr) >1:
3 mid = len(arr)//2 # Finding the mid of the array
4 L = arr[:mid] # Dividing the array elements
5 R = arr[mid:] # into 2 halves
6
7 mergeSort(L) # Sorting the first half
8 mergeSort(R) # Sorting the second half
9
10 i = j = k = 0
11
12 # Copy data to temp arrays L[] and R[]
13 while i < len(L) and j < len(R):
14 if L[i] < R[j]:
15 arr[k] = L[i]
16 i+= 1
17 else:
18 arr[k] = R[j]
19 j+= 1
20 k+= 1
21
22 # Checking if any element was left
23 while i < len(L):
24 arr[k] = L[i]
25 i+= 1
26 k+= 1
27
28 while j < len(R):
29 arr[k] = R[j]
30 j+= 1
31 k+= 1
32
33# Code to print the list
34def printList(arr):
35 for i in range(len(arr)):
36 print(arr[i], end =" ")
37 print()
38
39# driver code to test the above code
40if __name__ == '__main__':
41 arr = [12, 11, 13, 5, 6, 7]
42 print ("Given array is", end ="\n")
43 printList(arr)
44 mergeSort(arr)
45 print("Sorted array is: ", end ="\n")
46 printList(arr)