Guest User

Untitled

a guest
Jun 19th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. def merge_sort(arr):
  2. mergeSort(arr, 0, len(arr)-1)
  3. return arr
  4.  
  5. def merge(arr, l, m, r):
  6. if(arr[m] > arr[m+1]):
  7. #Left Buffer
  8. L = arr[l:m+1]
  9.  
  10. #Right Buffer
  11. R = arr[m+1:r+1]
  12.  
  13. # Merge the temp arrays back into arr[l..r]
  14.  
  15. i = 0 # Initial index of first subarray
  16. j = 0 # Initial index of second subarray
  17. k = l # Initial index of merged subarray
  18.  
  19. #Length of both the buffers
  20. len_l = m+1-l
  21. len_r = r-m
  22.  
  23. #Merging of two sorted subarrays
  24. while i < len_l and j < len_r:
  25. if L[i] <= R[j]:
  26. arr[k] = L[i]
  27. i += 1
  28. else:
  29. arr[k] = R[j]
  30. j += 1
  31. k += 1
  32.  
  33. #Copy if there are any elements in the left subarray
  34. #Note that the right subarray is already there and hence does not need to be copied
  35. while(i < len_l):
  36. arr[k] = L[i]
  37. i += 1
  38. k += 1
  39.  
  40. def mergeSort(arr,l, r):
  41. if l < r:
  42.  
  43. m = (l+r)//2
  44.  
  45. # Sort first and second subarray
  46. mergeSort(arr, l, m)
  47. mergeSort(arr, m+1, r)
  48.  
  49. #Merge both the subarrays
  50. merge(arr, l, m, r)
  51.  
  52. if __name__ == '__main__':
  53.  
  54. t = int(input())
  55. arr = []
  56. try:
  57. for t_itr in range(t):
  58. n = input()
  59. arr.append(n)
  60.  
  61. arr = list(map(int, arr))
  62.  
  63. result = merge_sort(arr)
  64. except:
  65. arr = list(map(int, n.rstrip().split()))
  66.  
  67. result = merge_sort(arr)
  68.  
  69. print(str(result).replace(" ", ""))
Add Comment
Please, Sign In to add comment