SHARE
TWEET

Untitled

a guest Nov 17th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def merge(arr, l, m, r):
  2.   l_length = (m - l) + 1
  3.   r_length = r - m
  4.  
  5.   left_half = [0]*l_length
  6.   right_half = [0]*r_length
  7.  
  8.   for i in range(0 , l_length):
  9.     left_half[i] = arr[l + i]
  10.  
  11.   for j in range(0 , r_length):
  12.     right_half[j] = arr[m + 1 + j]
  13.  
  14.   i = 0
  15.   j = 0
  16.   k = l
  17.  
  18.   while i < l_length and j < r_length :
  19.    
  20.     if left_half[i] <= right_half[j]:
  21.       arr[k] = left_half[i]
  22.       i += 1
  23.     else:
  24.       arr[k] = right_half[j]
  25.       j += 1
  26.     k += 1
  27.  
  28.   while i < l_length:
  29.     arr[k] = left_half[i]
  30.     i += 1
  31.     k += 1
  32.  
  33.  
  34.   while j < r_length:
  35.     arr[k] = right_half[j]
  36.     j += 1
  37.     k += 1
  38.   return arr
  39.  
  40. def merge_sort_helper(arr,l,r):
  41.   if l < r:
  42.  
  43.     m = (l+(r-1))//2
  44.     merge_sort_helper(arr, l, m)
  45.     merge_sort_helper(arr, m+1, r)
  46.  
  47.     return merge(arr, l, m, r)
  48.   else:
  49.     return arr
  50.  
  51. def mergeSort(arr):
  52.   return merge_sort_helper( arr, 0, len(arr)-1 )
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top