Advertisement
brainuser5705

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 = [1]
  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()
Advertisement
RAW Paste Data Copied
Advertisement