(customList, l, m, r)
| 73 | # MERGE SORT ALGORITHM |
| 74 | |
| 75 | def merge(customList, l, m, r): |
| 76 | n1 = m - l + 1 |
| 77 | n2 = r - m |
| 78 | |
| 79 | L =[0]*(n1) |
| 80 | R =[0]*(n2) |
| 81 | |
| 82 | for i in range(0,n1): |
| 83 | L[i] = customList[l+i] |
| 84 | |
| 85 | for j in range(0,n2): |
| 86 | R[j] = customList[m+1+j] |
| 87 | |
| 88 | i = 0 |
| 89 | j = 0 |
| 90 | k = l |
| 91 | while i < n1 and j <n2: |
| 92 | if L[i] <=R[j]: |
| 93 | customList[k] = L[i] |
| 94 | i += 1 |
| 95 | else: |
| 96 | customList[k] = R[j] |
| 97 | j += 1 |
| 98 | k += 1 |
| 99 | while i < n1: |
| 100 | customList[k] = L[i] |
| 101 | i += 1 |
| 102 | k += 1 |
| 103 | while j < n2: |
| 104 | customList[k] = R[j] |
| 105 | j += 1 |
| 106 | k += 1 |
| 107 | # TIME COMPLEXITY : O(N) |
| 108 | |
| 109 |