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))
1// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
2// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
3
4function merge(list, start, midpoint, end) {
5 const left = list.slice(start, midpoint);
6 const right = list.slice(midpoint, end);
7 for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
8 if (topLeft >= left.length) {
9 list[i] = right[topRight++];
10 } else if (topRight >= right.length) {
11 list[i] = left[topLeft++];
12 } else if (left[topLeft] < right[topRight]) {
13 list[i] = left[topLeft++];
14 } else {
15 list[i] = right[topRight++];
16 }
17 }
18}
19
20function mergesort(list, start = 0, end = undefined) {
21 if (end === undefined) {
22 end = list.length;
23 }
24 if (end - start > 1) {
25 const midpoint = ((end + start) / 2) >> 0;
26 mergesort(list, start, midpoint);
27 mergesort(list, midpoint, end);
28 merge(list, start, midpoint, end);
29 }
30 return list;
31}
32
33mergesort([4, 7, 2, 6, 4, 1, 8, 3]);
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