 # in place merge sort

Apr 20th, 2021
88
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from random import randrange
2.
3. arr = 
4.
5. def generate_random():
6.     for i in range(0,20):
7.         arr.append(randrange(0,20))
8.
9. def shift(s, e):
10.     end = arr[e]
11.     for i in range(e-1, s-1, -1):
12.         arr[i+1] = arr[i]
13.     arr[s] = end
14.
15. # def while_shift():
16. #     value = arr[start2]
17. #     index = start2
18.
19. #     # Shift all the elements between element 1
20. #     # element 2, right by 1.
21. #     while (index != start):
22. #         arr[index] = arr[index - 1]
23. #         index -= 1
24.
25. #     arr[start] = value
26.
27. def merge(p1, p2, end):
28.
29.     print("Pointer 1: "  + str(p1) + ", Pointer 2 " + str(p2))
30.
31.     # If the direct merge is already sorted (already sorted in the previous stack)
32.     if (arr[p2-1] <= arr[p2]):
33.         return
34.
35.     # Two pointers to maintain start
36.     # of both arrays to merge
37.     while (p1 <= p2-1 and p2 <= end):
38.
39.         # If element 1 is in right place
40.         if (arr[p1] <= arr[p2]):
41.             p1 += 1
42.         else:
43.             shift(p1, p2)
44.
45.             # Update all the pointers
46.             p1 += 1
47.             p2 += 1
48.
49.
50. def merge_sort(s, e):
51.     if s < e:
52.         m = (e - s) // 2 + s
53.
54.         # first half (s,m)
55.         merge_sort(s,m)
56.         # second half (m+1,e)
57.         merge_sort(m+1,e)
58.
59.         merge(s,m+1,e)
60.
61. def main():
62.     generate_random()
63.     print(arr)
64.     if len(arr) >= 1:
65.         merge_sort(0,len(arr)-1)
66.     print(arr)
67.
68. if __name__ == '__main__':
69.     main()