Given an array arr[], its starting position l and its ending position r. Sort the array using merge sort algorithm.
Example 1:
Input:
N = 5
arr[] = {4 1 3 9 7}
Output:
1 3 4 7 9
Example 2:
Input:
N = 10
arr[] = {10 9 8 7 6 5 4 3 2 1}
Output:
1 2 3 4 5 6 7 8 9 10
Your Task:
You don't need to take the input or print anything. Your task is to complete the function merge() which takes arr[], l, m, r as its input parameters and modifies arr[] in-place such that it is sorted from position l to position r, and function mergeSort() which uses merge() to sort the array in ascending order using merge sort algorithm.
Expected Time Complexity: O(nlogn) 
Expected Auxiliary Space: O(n)
Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Divide and conquer

Starter code: #User function Template for python3



class Solution:

    def merge(self,arr, l, m, r): 

        # code here

    def mergeSort(self,arr, l, r):

        #code here



Solutions:
class Solution:

	def merge(self, arr, l, m, r):
		left = arr[l:mid + 1]
		right = arr[mid + 1:r]
		i = j = 0
		k = l
		while i < len(left) and j < len(right):
			if left[i] < right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
			k += 1
		while i < len(left):
			arr[k] = left[i]
			i += 1
			k += 1
		while j < len(right):
			arr[k] = right[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			mid = (l + r) // 2
			self.mergeSort(arr, l, mid)
			self.mergeSort(arr, mid + 1, r)
			left = arr[l:mid + 1]
			right = arr[mid + 1:r + 1]
			i = j = 0
			k = l
			while i < len(left) and j < len(right):
				if left[i] < right[j]:
					arr[k] = left[i]
					i += 1
				else:
					arr[k] = right[j]
					j += 1
				k += 1
			while i < len(left):
				arr[k] = left[i]
				i += 1
				k += 1
			while j < len(right):
				arr[k] = right[j]
				j += 1
				k += 1


class Solution:

	def merge(self, arr, l, m, r):
		low = l
		high = r
		temp = []
		mid = m + 1
		ind = 0
		while l <= m and mid <= r:
			if arr[l] <= arr[mid]:
				temp.append(arr[l])
				l += 1
			else:
				temp.append(arr[mid])
				mid += 1
		while l <= m:
			temp.append(arr[l])
			l += 1
		while mid <= r:
			temp.append(arr[mid])
			mid += 1
		for i in range(low, high + 1):
			arr[i] = temp[i - low]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr, l, m, r):
		temp = []
		left = l
		right = m + 1
		while left <= m and right <= r:
			if arr[left] <= arr[right]:
				temp.append(arr[left])
				left += 1
			else:
				temp.append(arr[right])
				right += 1
		while left <= m:
			temp.append(arr[left])
			left += 1
		while right <= r:
			temp.append(arr[right])
			right += 1
		for i in range(l, r + 1):
			arr[i] = temp[i - l]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		m = (l + r) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		tmp = [0] * (r - l + 1)
		i = l
		j = m + 1
		k = 0
		while i <= m and j <= r:
			if arr[i] < arr[j]:
				tmp[k] = arr[i]
				i += 1
			else:
				tmp[k] = arr[j]
				j += 1
			k += 1
		while i <= m:
			tmp[k] = arr[i]
			i += 1
			k += 1
		while j <= r:
			tmp[k] = arr[j]
			j += 1
			k += 1
		k = 0
		for i in range(l, r + 1):
			arr[i] = tmp[k]
			k += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)
		return


class Solution:

	def merge(self, arr, l, m, r):
		i = l
		j = m + 1
		temparr = []
		while i <= m and j <= r:
			if arr[i] < arr[j]:
				temparr.append(arr[i])
				i += 1
			else:
				temparr.append(arr[j])
				j += 1
		while i <= m:
			temparr.append(arr[i])
			i += 1
		while j <= r:
			temparr.append(arr[j])
			j += 1
		arr[l:r + 1] = temparr
		return

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)
		return


class Solution:

	def merge(self, arr, l, m, r):
		temp_arr = []
		left_arr_index = l
		right_arr_index = m + 1
		while left_arr_index <= m and right_arr_index <= r:
			if arr[left_arr_index] <= arr[right_arr_index]:
				temp_arr.append(arr[left_arr_index])
				left_arr_index += 1
			else:
				temp_arr.append(arr[right_arr_index])
				right_arr_index += 1
		while left_arr_index <= m:
			temp_arr.append(arr[left_arr_index])
			left_arr_index += 1
		while right_arr_index <= r:
			temp_arr.append(arr[right_arr_index])
			right_arr_index += 1
		for index in range(l, r + 1):
			arr[index] = temp_arr[index - l]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def mergeSort(self, arr, l, r):
		if len(arr) > 1:
			m = len(arr) // 2
			leftArr = arr[:m]
			rightArr = arr[m:]
			self.mergeSort(leftArr, l, m - 1)
			self.mergeSort(rightArr, m, r)
			i = j = k = 0
			while i < len(leftArr) and j < len(rightArr):
				if leftArr[i] < rightArr[j]:
					arr[k] = leftArr[i]
					i += 1
				else:
					arr[k] = rightArr[j]
					j += 1
				k += 1
			while i < len(leftArr):
				arr[k] = leftArr[i]
				i += 1
				k += 1
			while j < len(rightArr):
				arr[k] = rightArr[j]
				j += 1
				k += 1


class Solution:

	def mergeSort(self, arr, l, r):
		if len(arr) > 1:
			mid = len(arr) // 2
			L = arr[:mid]
			R = arr[mid:]
			self.mergeSort(L, l, r)
			self.mergeSort(R, l, r)
			i = j = k = 0
			while i < len(L) and j < len(R):
				if R[j] >= L[i]:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
				k += 1
			while i < len(L):
				arr[k] = L[i]
				i += 1
				k += 1
			while j < len(R):
				arr[k] = R[j]
				j += 1
				k += 1
			return
		return


class Solution:

	def merge(self, arr, l, mid, r):
		arr1 = arr[l:mid + 1]
		arr2 = arr[mid + 1:r + 1]
		i = 0
		j = 0
		k = l
		while i < len(arr1) and j < len(arr2):
			if arr1[i] <= arr2[j]:
				arr[k] = arr1[i]
				k += 1
				i += 1
			else:
				arr[k] = arr2[j]
				k += 1
				j += 1
		while i < len(arr1):
			arr[k] = arr1[i]
			i += 1
			k += 1
		while j < len(arr2):
			arr[k] = arr2[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr, l, m, r):
		n1 = m - l + 1
		n2 = r - m
		L = [0] * n1
		R = [0] * n2
		for i in range(0, n1):
			L[i] = arr[l + i]
		for j in range(0, n2):
			R[j] = arr[m + 1 + j]
		i = j = 0
		k = l
		while i < n1 and j < n2:
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = L[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = R[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			m = l + (r - l) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		a = l
		b = m + 1
		t = [0] * (r - l + 1)
		j = 0
		while a <= m and b <= r:
			if arr[a] <= arr[b]:
				t[j] = arr[a]
				a += 1
				j += 1
			else:
				t[j] = arr[b]
				b += 1
				j += 1
		while a <= m:
			t[j] = arr[a]
			a += 1
			j += 1
		while b <= r:
			t[j] = arr[b]
			b += 1
			j += 1
		for i in range(l, r + 1):
			arr[i] = t[i - l]

	def mergeSort(self, arr, l, r):
		if l == r:
			return
		m = l + (r - l) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		pass

	def mergeSort(self, arr, l, r):
		arr.sort()
		return arr


class Solution:

	def merge(self, arr, l, m, r):
		ls = l
		rs = m + 1
		temp = []
		while ls <= m and rs <= r:
			if arr[ls] > arr[rs]:
				temp.append(arr[rs])
				rs += 1
			else:
				temp.append(arr[ls])
				ls += 1
		for i in range(ls, m + 1):
			temp.append(arr[i])
		for i in range(rs, r + 1):
			temp.append(arr[i])
		for i in range(l, r + 1):
			arr[i] = temp[i - l]

	def mergeSort(self, arr, l, r):
		if l == r:
			return
		m = int((l + r) / 2)
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		aux = []
		ptr1 = l
		ptr2 = m + 1
		while ptr1 <= m and ptr2 <= r:
			if arr[ptr1] <= arr[ptr2]:
				aux.append(arr[ptr1])
				ptr1 += 1
			else:
				aux.append(arr[ptr2])
				ptr2 += 1
		while ptr1 <= m:
			aux.append(arr[ptr1])
			ptr1 += 1
		while ptr2 <= r:
			aux.append(arr[ptr2])
			ptr2 += 1
		count = 0
		for i in range(l, r + 1):
			arr[i] = aux[count]
			count += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = l + (r - l) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr, low, mid, high):
		temp = []
		left = low
		right = mid + 1
		while left <= mid and right <= high:
			if arr[left] <= arr[right]:
				temp.append(arr[left])
				left += 1
			else:
				temp.append(arr[right])
				right += 1
		while left <= mid:
			temp.append(arr[left])
			left += 1
		while right <= high:
			temp.append(arr[right])
			right += 1
		for i in range(low, high + 1):
			arr[i] = temp[i - low]

	def mergeSort(self, arr, low, high):
		if low >= high:
			return
		mid = (low + high) // 2
		self.mergeSort(arr, low, mid)
		self.mergeSort(arr, mid + 1, high)
		self.merge(arr, low, mid, high)


class Solution:

	def merge(self, arr, l, mid, r):
		n1 = mid - l + 1
		n2 = r - mid
		l1 = [0] * n1
		r1 = [0] * n2
		for i in range(n1):
			l1[i] = arr[l + i]
		for j in range(n2):
			r1[j] = arr[mid + 1 + j]
		i = 0
		j = 0
		k = l
		while i < n1 and j < n2:
			if l1[i] <= r1[j]:
				arr[k] = l1[i]
				i += 1
			else:
				arr[k] = r1[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = l1[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = r1[j]
			j += 1
			k += 1
		return

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = l + (r - l) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr, l, m, r):
		i = l
		j = m + 1
		k = 0
		arr_tmp = []
		while i <= m and j <= r:
			if arr[i] <= arr[j]:
				arr_tmp.append(arr[i])
				i += 1
			else:
				arr_tmp.append(arr[j])
				j += 1
		while i <= m:
			arr_tmp.append(arr[i])
			i += 1
		while j <= r:
			arr_tmp.append(arr[j])
			j += 1
		for i in range(l, r + 1):
			arr[i] = arr_tmp[i - l]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		else:
			m = int(l + (r - l) / 2)
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		tmp = []
		mid = m
		first = l
		second = mid + 1
		while first <= mid and second <= r:
			if arr[first] < arr[second]:
				tmp.append(arr[first])
				first = first + 1
			elif arr[first] > arr[second]:
				tmp.append(arr[second])
				second = second + 1
			else:
				tmp.append(arr[first])
				tmp.append(arr[second])
				first = first + 1
				second = second + 1
		while first <= mid:
			tmp.append(arr[first])
			first = first + 1
		while second <= r:
			tmp.append(arr[second])
			second = second + 1
		for i in range(len(tmp)):
			arr[l + i] = tmp[i]

	def mergeSort(self, arr, l, r):
		if l < r:
			mid = (l + r) // 2
			self.mergeSort(arr, l, mid)
			self.mergeSort(arr, mid + 1, r)
			self.merge(arr, l, mid, r)
		return arr


class Solution:

	def merge(self, arr, l, m, r):
		lArr = (arr[:m + 1], rArr) = arr[m:]
		left = right = k = 0
		while left < len(lArr) and right < len(rArr):
			if lArr[left] < rArr[right]:
				arr[k] = lArr[left]
				left += 1
			else:
				arr[k] = rArr[right]
				right += 1
			k += 1
		while left < len(lArr):
			arr[k] = lArr[left]
			k += 1
			left += 1
		while right < len(rArr):
			arr[k] = rArr[right]
			k += 1
			right += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)

class Solution:

	def merge(self, arr, l, m, r):
		n1 = arr[l:m + 1]
		n2 = arr[m + 1:r + 1]
		i = 0
		j = 0
		k = l
		while i < len(n1) and j < len(n2):
			if n1[i] <= n2[j]:
				arr[k] = n1[i]
				i += 1
			else:
				arr[k] = n2[j]
				j += 1
			k += 1
		while i < len(n1):
			arr[k] = n1[i]
			i += 1
			k += 1
		while j < len(n2):
			arr[k] = n2[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		m = (l + r) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		merge_arr = [0] * (r - l + 1)
		(i, j) = (l, m + 1)
		k = 0
		while i <= m and j <= r:
			if arr[i] <= arr[j]:
				merge_arr[k] = arr[i]
				i += 1
			else:
				merge_arr[k] = arr[j]
				j += 1
			k += 1
		while i <= m:
			merge_arr[k] = arr[i]
			i += 1
			k += 1
		while j <= r:
			merge_arr[k] = arr[j]
			j += 1
			k += 1
		k = l
		for num in merge_arr:
			arr[k] = num
			k += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			m = l + (r - l) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		arr_1 = arr[l:m + 1]
		arr_2 = arr[m + 1:r + 1]
		a_idx = 0
		b_idx = 0
		arr_cur_idx = l
		while a_idx < len(arr_1) and b_idx < len(arr_2):
			if arr_1[a_idx] <= arr_2[b_idx]:
				arr[arr_cur_idx] = arr_1[a_idx]
				a_idx += 1
			else:
				arr[arr_cur_idx] = arr_2[b_idx]
				b_idx += 1
			arr_cur_idx += 1
		while a_idx < len(arr_1):
			arr[arr_cur_idx] = arr_1[a_idx]
			a_idx += 1
			arr_cur_idx += 1
		while b_idx < len(arr_2):
			arr[arr_cur_idx] = arr_2[b_idx]
			b_idx += 1
			arr_cur_idx += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			m = l + (r - l) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


from collections import deque

class Solution:

	def _merge(self, left_que, right_que):
		res = deque()
		while left_que or right_que:
			if left_que and right_que:
				if left_que[0] <= right_que[0]:
					res.append(left_que.popleft())
				else:
					res.append(right_que.popleft())
			elif not right_que:
				res.append(left_que.popleft())
			else:
				res.append(right_que.popleft())
		return res

	def mergeSort(self, arr, l, r):
		queue = deque()
		for ele in arr:
			queue.append(deque([ele]))
		while len(queue) > 1:
			left_que = queue.popleft()
			right_que = queue.popleft()
			merged_que = self._merge(left_que, right_que)
			queue.append(merged_que)
		arr[:] = list(queue.pop())


class Solution:

	def merge(self, arr, l, m, r):
		left_arr = arr[l:m + 1]
		right_arr = arr[m + 1:r + 1]
		left_ptr = 0
		right_ptr = 0
		for ind in range(l, r + 1):
			if left_ptr == len(left_arr) or right_ptr == len(right_arr):
				if right_ptr == len(right_arr):
					arr[ind] = left_arr[left_ptr]
					left_ptr += 1
				else:
					arr[ind] = right_arr[right_ptr]
					right_ptr += 1
			elif left_arr[left_ptr] <= right_arr[right_ptr]:
				arr[ind] = left_arr[left_ptr]
				left_ptr += 1
			else:
				arr[ind] = right_arr[right_ptr]
				right_ptr += 1

	def mergeSort(self, arr, l, r):
		if l == r:
			return
		m = (l + r) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		i = l
		j = m + 1
		ans = []
		while i <= m and j <= r:
			if arr[i] < arr[j]:
				ans.append(arr[i])
				i += 1
			else:
				ans.append(arr[j])
				j += 1
		while i <= m:
			ans.append(arr[i])
			i += 1
		while j <= r:
			ans.append(arr[j])
			j += 1
		for i in range(r - l + 1):
			arr[l] = ans[i]
			l += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr, l, m, r):
		arr.sort()

	def mergeSort(self, arr, l, r):
		arr.sort()


class Solution:

	def merge(self, arr, l, m, r):
		list1 = arr[l:m + 1]
		list2 = arr[m + 1:r + 1]
		l1 = len(list1)
		l2 = len(list2)
		i = j = 0
		k = l
		while i < l1 and j < l2:
			if list1[i] <= list2[j]:
				arr[k] = list1[i]
				i += 1
			else:
				arr[k] = list2[j]
				j += 1
			k += 1
		while i < l1:
			arr[k] = list1[i]
			i += 1
			k += 1
		while j < l2:
			arr[k] = list2[j]
			j += 1
			k += 1
		return arr

	def mergeSort(self, arr, l, r):
		if l < r:
			m = (l + r) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def mergeSort(self, arr, l, r):
		if l < r:
			m = (l + r) // 2
			left_half = arr[l:m + 1]
			right_half = arr[m + 1:r + 1]
			self.mergeSort(left_half, 0, m - l)
			self.mergeSort(right_half, 0, r - m - 1)
			i = j = k = 0
			while i < len(left_half) and j < len(right_half):
				if left_half[i] < right_half[j]:
					arr[l + k] = left_half[i]
					i += 1
				else:
					arr[l + k] = right_half[j]
					j += 1
				k += 1
			while i < len(left_half):
				arr[l + k] = left_half[i]
				i += 1
				k += 1
			while j < len(right_half):
				arr[l + k] = right_half[j]
				j += 1
				k += 1
		return arr


class Solution:

	def merge(self, arr, l, mid, r):
		i = l
		j = mid + 1
		temp = list(range(r - l + 1))
		k = 0
		while i <= mid and j <= r:
			if arr[i] <= arr[j]:
				temp[k] = arr[i]
				i += 1
			else:
				temp[k] = arr[j]
				j += 1
			k += 1
		while i <= mid:
			temp[k] = arr[i]
			i += 1
			k += 1
		while j <= r:
			temp[k] = arr[j]
			j += 1
			k += 1
		arr[l:r + 1] = temp

	def mergeSort(self, arr, l, r):
		if r - l > 0:
			mid = (r + l) // 2
			self.mergeSort(arr, l, mid)
			self.mergeSort(arr, mid + 1, r)
			self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr, l, m, r):
		arr1 = []
		st = l
		end = m + 1
		while st <= m and end <= r:
			if arr[st] < arr[end]:
				arr1.append(arr[st])
				st += 1
			else:
				arr1.append(arr[end])
				end += 1
		while st <= m:
			arr1.append(arr[st])
			st += 1
		while end <= r:
			arr1.append(arr[end])
			end += 1
		for i in range(l, r + 1):
			arr[i] = arr1[i - l]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		m = (l + r) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def mergeSort(self, arr, l, r):
		if l == r:
			return l
		mid = (l + r) // 2
		left = self.mergeSort(arr, l, mid)
		right = self.mergeSort(arr, mid + 1, r)
		temp = []
		while left <= mid and right <= r:
			if arr[left] < arr[right]:
				temp.append(arr[left])
				left += 1
			else:
				temp.append(arr[right])
				right += 1
		while left <= mid:
			temp.append(arr[left])
			left += 1
		while right <= r:
			temp.append(arr[right])
			right += 1
		pointer = 0
		for index in range(l, r + 1):
			arr[index] = temp[pointer]
			pointer += 1
		return l


import copy

class Solution:

	def merge(self, arr, l, m, r):
		(n1, n2) = (m - l + 1, r - m)
		(left, rigth) = ([0] * n1, [0] * n2)
		for i in range(0, n1):
			left[i] = arr[l + i]
		for j in range(0, n2):
			rigth[j] = arr[m + 1 + j]
		(i, j, k) = (0, 0, l)
		while i < n1 and j < n2:
			if left[i] <= rigth[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = rigth[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = rigth[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			m = l + (r - l) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, mid, r):
		temp = []
		low = l
		high = mid + 1
		while low <= mid and high <= r:
			if arr[low] < arr[high]:
				temp.append(arr[low])
				low += 1
			else:
				temp.append(arr[high])
				high += 1
		while low <= mid:
			temp.append(arr[low])
			low += 1
		while high <= r:
			temp.append(arr[high])
			high += 1
		arr[l:r + 1] = temp[:]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)
		return arr


class Solution:

	def merge(self, arr, low, mid, high):
		res = []
		(p1, p2) = (low, mid + 1)
		while p1 <= mid and p2 <= high:
			if arr[p1] < arr[p2]:
				res.append(arr[p1])
				p1 += 1
			else:
				res.append(arr[p2])
				p2 += 1
		while p1 <= mid:
			res.append(arr[p1])
			p1 += 1
		while p2 <= high:
			res.append(arr[p2])
			p2 += 1
		arr[low:high + 1] = res[:]

	def mergeSort(self, arr, low, high):
		if low >= high:
			return
		mid = (low + high) // 2
		Solution.mergeSort(self, arr, low, mid)
		Solution.mergeSort(self, arr, mid + 1, high)
		Solution.merge(self, arr, low, mid, high)
		return arr


class Solution:

	def merge(self, arr, l, m, r):
		left = [0] * (m - l + 1)
		right = [0] * (r - m)
		n1 = m - l + 1
		n2 = r - m
		for i in range(0, m - l + 1):
			left[i] = arr[l + i]
		for j in range(0, r - m):
			right[j] = arr[m + 1 + j]
		i = 0
		j = 0
		k = l
		while i < n1 and j < n2:
			if left[i] < right[j]:
				arr[k] = left[i]
				i += 1
			else:
				arr[k] = right[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = left[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = right[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			p = l + (r - l) // 2
			self.mergeSort(arr, l, p)
			self.mergeSort(arr, p + 1, r)
			self.merge(arr, l, p, r)


class Solution:

	def merge(self, arr, l, m, r):
		i1 = l
		i2 = m + 1
		ix = 0
		temp = [0] * (r - l + 1)
		while i1 <= m and i2 <= r:
			if arr[i1] < arr[i2]:
				temp[ix] = arr[i1]
				i1 += 1
			else:
				temp[ix] = arr[i2]
				i2 += 1
			ix += 1
		while i1 <= m:
			temp[ix] = arr[i1]
			i1 += 1
			ix += 1
		while i2 <= r:
			temp[ix] = arr[i2]
			i2 += 1
			ix += 1
		ix = l
		for i in range(len(temp)):
			arr[ix] = temp[i]
			ix += 1

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		self.mergeSort(arr, l, mid)
		self.mergeSort(arr, mid + 1, r)
		self.merge(arr, l, mid, r)


class Solution:

	def merge(self, arr):
		if len(arr) > 1:
			mid = len(arr) // 2
			leftSubArray = arr[:mid]
			rightSubArray = arr[mid:]
			self.merge(leftSubArray)
			self.merge(rightSubArray)
			i = j = k = 0
			while i < len(leftSubArray) and j < len(rightSubArray):
				if leftSubArray[i] < rightSubArray[j]:
					arr[k] = leftSubArray[i]
					i += 1
				else:
					arr[k] = rightSubArray[j]
					j += 1
				k += 1
			while i < len(leftSubArray):
				arr[k] = leftSubArray[i]
				i += 1
				k += 1
			while j < len(rightSubArray):
				arr[k] = rightSubArray[j]
				j += 1
				k += 1

	def mergeSort(self, arr, l, r):
		self.merge(arr)


class Solution:

	def merge(self, arr, l, m, r):
		L = arr[l:m + 1]
		R = arr[m + 1:r + 1]
		(i, j, k) = (0, 0, 0)
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[l + k] = L[i]
				i += 1
			else:
				arr[l + k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[l + k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[l + k] = R[j]
			j += 1
			k += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			m = (l + r) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		sorted_arr = [0] * (r - l + 1)
		i = l
		k = 0
		j = m + 1
		while i < m + 1 and j < r + 1:
			if arr[i] <= arr[j]:
				sorted_arr[k] = arr[i]
				i += 1
			else:
				sorted_arr[k] = arr[j]
				j += 1
			k += 1
		while i < m + 1:
			sorted_arr[k] = arr[i]
			i += 1
			k += 1
		while j < r + 1:
			sorted_arr[k] = arr[j]
			j += 1
			k += 1
		arr[l:r + 1] = sorted_arr[:]

	def mergeSort(self, arr, l, r):
		if r - l + 1 < 2:
			return
		m = l + (r - l) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution(object):

	def mergeSort(self, nums, l, r):
		temp = [0] * len(nums)
		return self.mergeSortHelper(nums, temp, 0, len(nums) - 1)

	def mergeSortHelper(self, nums, temp, left, right):
		if left < right:
			mid = (left + right) // 2
			self.mergeSortHelper(nums, temp, left, mid)
			self.mergeSortHelper(nums, temp, mid + 1, right)
			self.merge(nums, temp, left, mid + 1, right)
		return nums

	def merge(self, nums, temp, left, mid, right):
		i = left
		j = mid
		k = left
		while i <= mid - 1 and j <= right:
			if nums[i] <= nums[j]:
				temp[k] = nums[i]
				i += 1
				k += 1
			else:
				temp[k] = nums[j]
				j += 1
				k += 1
		while i <= mid - 1:
			temp[k] = nums[i]
			i += 1
			k += 1
		while j <= right:
			temp[k] = nums[j]
			j += 1
			k += 1
		for index in range(left, right + 1):
			nums[index] = temp[index]
		return nums


class Solution:

	def merge(self, arr, l, m, r):
		pass

	def mergeSort(self, arr, l, r):
		p = sorted(arr)
		for i in range(len(arr)):
			arr[i] = p[i]


class Solution:

	def merge(self, arr, l, m, r):
		temp = []
		li = l
		ri = m + 1
		while li <= m and ri <= r:
			if arr[li] <= arr[ri]:
				temp.append(arr[li])
				li = li + 1
			else:
				temp.append(arr[ri])
				ri = ri + 1
		while li <= m:
			temp.append(arr[li])
			li = li + 1
		while ri <= r:
			temp.append(arr[ri])
			ri = ri + 1
		for i in range(l, r + 1):
			arr[i] = temp[i - l]

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		mid = (l + r) // 2
		Solution.mergeSort(self, arr, l, mid)
		Solution.mergeSort(self, arr, mid + 1, r)
		Solution.merge(self, arr, l, mid, r)


class Solution:

	def merge(self, arr, l, m, r):
		temp = []
		i = l
		j = m + 1
		idx = l
		while i <= m and j <= r:
			if arr[i] < arr[j]:
				temp.append(arr[i])
				i += 1
			else:
				temp.append(arr[j])
				j += 1
		while i <= m:
			temp.append(arr[i])
			i += 1
		while j <= r:
			temp.append(arr[j])
			j += 1
		for i in range(len(temp)):
			num = temp[i]
			arr[l + i] = num

	def mergeSort(self, arr, l, r):
		if l < r:
			m = l + (r - l) // 2
			self.mergeSort(arr, l, m)
			self.mergeSort(arr, m + 1, r)
			self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		leftarray = arr[l:m + 1]
		rightarray = arr[m + 1:r + 1]
		k = l
		i = l
		j = m + 1
		while i <= m and j <= r:
			if leftarray[i - l] < rightarray[j - (m + 1)]:
				arr[k] = leftarray[i - l]
				i = i + 1
			else:
				arr[k] = rightarray[j - (m + 1)]
				j = j + 1
			k = k + 1
		while i < m + 1:
			arr[k] = leftarray[i - l]
			i = i + 1
			k = k + 1
		while j < r + 1:
			arr[k] = rightarray[j - (m + 1)]
			j = j + 1
			k = k + 1
		return

	def mergeSort(self, arr, l, r):
		if l >= r:
			return
		m = (l + r) // 2
		self.mergeSort(arr, l, m)
		self.mergeSort(arr, m + 1, r)
		self.merge(arr, l, m, r)


class Solution:

	def merge(self, arr, l, m, r):
		(p, q) = (l, m + 1)
		res = []
		while p <= m and q <= r:
			if arr[p] <= arr[q]:
				res.append(arr[p])
				p += 1
			else:
				res.append(arr[q])
				q += 1
		if p > m:
			while q <= r:
				res.append(arr[q])
				q += 1
		if q > r:
			while p <= m:
				res.append(arr[p])
				p += 1
		for each in res:
			arr[l] = each
			l += 1

	def mergeSort(self, arr, l, r):
		if l < r:
			mid = (l + r) // 2
			self.mergeSort(arr, l, mid)
			self.mergeSort(arr, mid + 1, r)
			self.merge(arr, l, mid, r)