Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.
Example 1:
Input: 
n = 4, arr1[] = [1 3 5 7] 
m = 5, arr2[] = [0 2 6 8 9]
Output: 
arr1[] = [0 1 2 3]
arr2[] = [5 6 7 8 9]
Explanation:
After merging the two 
non-decreasing arrays, we get, 
0 1 2 3 5 6 7 8 9.
Example 2:
Input: 
n = 2, arr1[] = [10 12] 
m = 3, arr2[] = [5 18 20]
Output: 
arr1[] = [5 10]
arr2[] = [12 18 20]
Explanation:
After merging two sorted arrays 
we get 5 10 12 18 20.
Your Task:
You don't need to read input or print anything. You only need to complete the function merge() that takes arr1, arr2, n and m as input parameters and modifies them in-place so that they look like the sorted merged array when concatenated.
Expected Time Complexity:  O((n+m) log(n+m))
Expected Auxilliary Space: O(1)
Constraints:
1 <= n, m <= 10^{5}
0 <= arr1_{i}, arr2_{i} <= 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics

Starter code: #User function Template for python3



class Solution:

    

    #Function to merge the arrays.

    def merge(self,arr1,arr2,n,m):

        #code here

    



Solutions:
class Solution:

	def merge(self, arr1, arr2, n, m):
		left = n - 1
		right = 0
		while left >= 0 and right < m:
			if arr1[left] > arr2[right]:
				(arr1[left], arr2[right]) = (arr2[right], arr1[left])
				left -= 1
				right += 1
			else:
				break
		arr1.sort()
		arr2.sort()


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr1.extend(arr2)
		arr1.sort()
		arr2.clear()
		return arr1


class Solution:

	def merge(self, arr1, arr2, n, m):
		(i, j) = (n - 1, 0)
		while i >= 0 and j < m:
			if arr1[i] > arr2[j]:
				(arr1[i], arr2[j]) = (arr2[j], arr1[i])
				i -= 1
				j += 1
			else:
				break
		arr1.sort()
		arr2.sort()


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr3 = arr1 + arr2
		arr3.sort()
		i = 0
		k = 0
		while i < n:
			arr1[i] = arr3[i]
			i = i + 1
			k = k + 1
		i = 0
		while i < m:
			arr2[i] = arr3[k]
			i = i + 1
			k = k + 1


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr = arr1 + arr2
		arr.sort()
		for i in range(n):
			arr1[i] = arr[i]
		for j in range(m):
			arr2[j] = arr[j + n]


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr = sorted(arr1 + arr2)
		for i in range(n):
			arr1.pop(0)
			arr1.append(arr[i])
		for i in range(m):
			arr2.pop(0)
			arr2.append(arr[i + n])


class Solution:

	def merge(self, arr1, arr2, n, m):
		i = 0
		j = n - 1
		while i < m and arr1[j] > arr2[i]:
			(arr1[j], arr2[i]) = (arr2[i], arr1[j])
			i += 1
			j -= 1
		arr1.sort()
		arr2.sort()
		return (arr1, arr2)


class Solution:

	def merge(self, arr1, arr2, n, m):
		i = 0
		j = 0
		k = 0
		merged = [0] * (n + m)
		while i < n and j < m:
			if arr1[i] <= arr2[j]:
				merged[k] = arr1[i]
				i += 1
			else:
				merged[k] = arr2[j]
				j += 1
			k += 1
		while i < n:
			merged[k] = arr1[i]
			i += 1
			k += 1
		while j < m:
			merged[k] = arr2[j]
			j += 1
			k += 1
		for i in range(n):
			arr1[i] = merged[i]
		for j in range(m):
			arr2[j] = merged[n + j]


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr1.sort()
		arr2.sort()
		k = 0
		i = 0
		j = 0
		arr = []
		while k < n + m:
			if i < n and (j >= m or arr1[i] <= arr2[j]):
				arr.append(arr1[i])
				i += 1
			else:
				arr.append(arr2[j])
				j += 1
			k += 1
		for i in range(n):
			arr1[i] = arr[i]
		for i in range(m):
			arr2[i] = arr[n + i]


class Solution:

	def merge(self, a1, a2, n, m):
		(i, j) = (n - 1, 0)
		while i >= 0 and j < m:
			if a1[i] > a2[j]:
				(a1[i], a2[j]) = (a2[j], a1[i])
			i -= 1
			j += 1
		a1.sort()
		a2.sort()


class Solution:

	def merge(self, arr1, arr2, n, m):
		l = []
		k = []
		l.extend(arr1)
		l.extend(arr2)
		l.sort()
		for i in range(n):
			arr1[i] = l[i]
		for j in range(m):
			arr2[j] = l[j + n]
		k = arr1 + arr2
		return k


class Solution:

	def merge(self, arr1, arr2, n, m):
		x = [arr1[i] for i in range(0, n)]
		for i in range(0, m):
			x.append(arr2[i])
		x.sort()
		for i in range(0, n):
			arr1[i] = x[i]
		for i in range(0, m):
			arr2[i] = x[n + i]


class Solution:

	def merge(self, arr1, arr2, n, m):
		for i in arr2:
			arr1.append(i)
		arr1.sort()
		arr2.clear()


class Solution:

	def merge(self, arr1, arr2, n, m):
		for i in range(0, len(arr1)):
			mini = arr2[0]
			if arr1[i] >= mini:
				arr1.insert(i, mini)
				arr2.remove(mini)
				arr2.append(arr1[-1])
				arr1.pop()
		arr2.sort()


class Solution:

	def merge(self, arr1, arr2, n, m):
		a = arr2 + arr1
		a.sort()
		ans1 = []
		ans2 = []
		for i in range(n):
			arr1[i] = a[i]
		for i in range(m):
			arr2[i] = a[n + i]


class Solution:

	def nextGap(self, gap):
		if gap <= 1:
			return 0
		return (gap + 1) // 2

	def merge(self, arr1, arr2, n, m):
		gap = n + m
		gap = self.nextGap(gap)
		while gap > 0:
			i = 0
			while i + gap < n:
				if arr1[i] > arr1[i + gap]:
					(arr1[i], arr1[i + gap]) = (arr1[i + gap], arr1[i])
				i += 1
			j = max(0, gap - n)
			while i < n and j < m:
				if arr1[i] > arr2[j]:
					(arr1[i], arr2[j]) = (arr2[j], arr1[i])
				i += 1
				j += 1
			if j < m:
				j = 0
				while j + gap < m:
					if arr2[j] > arr2[j + gap]:
						(arr2[j], arr2[j + gap]) = (arr2[j + gap], arr2[j])
					j += 1
			gap = self.nextGap(gap)


class Solution:

	def merge(self, arr1, arr2, n, m):
		l = n - 1
		r = 0
		while l >= 0 and r < m:
			if arr1[l] > arr2[r]:
				(arr1[l], arr2[r]) = (arr2[r], arr1[l])
				l -= 1
				r += 1
			else:
				break
		arr1.sort()
		arr2.sort()


class Solution:

	def __init__(self):
		self.radix = 100000000.0

	def get(self, arr, ind, original=True):
		if original:
			return arr[ind] % self.radix
		else:
			return arr[ind] // self.radix

	def modifyAndStore(self, arr1, arr2, n, m, ind, val):
		if ind < n:
			arr1[ind] = val * self.radix + arr1[ind]
		else:
			arr2[ind - n] = val * self.radix + arr2[ind - n]

	def merge(self, arr1, arr2, n, m):
		i = 0
		j = 0
		ind = 0
		while i < n and j < m:
			if self.get(arr1, i) < self.get(arr2, j):
				self.modifyAndStore(arr1, arr2, n, m, ind, self.get(arr1, i))
				i += 1
				ind += 1
			else:
				self.modifyAndStore(arr1, arr2, n, m, ind, self.get(arr2, j))
				j += 1
				ind += 1
		while i < n:
			self.modifyAndStore(arr1, arr2, n, m, ind, self.get(arr1, i))
			i += 1
			ind += 1
		while j < m:
			self.modifyAndStore(arr1, arr2, n, m, ind, self.get(arr2, j))
			j += 1
			ind += 1
		for i in range(n):
			arr1[i] = int(self.get(arr1, i, False))
		for i in range(m):
			arr2[i] = int(self.get(arr2, i, False))


class Solution:

	def merge(self, a, b, n, m):
		i = n - 1
		j = 0
		while i >= 0 and j < m and (a[i] > b[j]):
			(a[i], b[j]) = (b[j], a[i])
			i -= 1
			j += 1
		a.sort()
		b.sort()


class Solution:

	def merge(self, arr1, arr2, n, m):
		l = arr1.copy()
		arr1.extend(arr2)
		arr1.sort()
		i = 0
		while i < m:
			arr1.pop()
			i = i + 1
		arr2.extend(l)
		arr2.sort()
		for item in arr1:
			if item in arr2:
				arr2.remove(item)


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr3 = [0] * (n + m)
		k = 0
		for i in range(n):
			arr3[k] = arr1[i]
			k += 1
		for i in range(m):
			arr3[k] = arr2[i]
			k += 1
		arr3.sort()
		k = 0
		for i in range(n):
			arr1[i] = arr3[k]
			k += 1
		for i in range(m):
			arr2[i] = arr3[k]
			k += 1


class Solution:

	def merge(self, arr1, arr2, n, m):
		(i, j) = (0, 0)
		while i < len(arr1) and j < len(arr2):
			if arr1[i] > arr2[j]:
				arr1.insert(i, arr2[j])
				j += 1
				i += 1
			else:
				i += 1
		arr1.extend(arr2[j:])
		arr2[:] = []


import math

class Solution:

	def merge(self, arr1, arr2, m, n):
		gap = math.ceil((m + n) / 2)
		while gap >= 1:
			(i, j) = (0, gap)
			while j < m:
				if arr1[i] > arr1[j]:
					(arr1[i], arr1[j]) = (arr1[j], arr1[i])
				i += 1
				j += 1
			j = 0
			while i < m and j < n:
				if arr1[i] > arr2[j]:
					(arr1[i], arr2[j]) = (arr2[j], arr1[i])
				i += 1
				j += 1
			i = 0
			while j < n:
				if arr2[i] > arr2[j]:
					(arr2[i], arr2[j]) = (arr2[j], arr2[i])
				i += 1
				j += 1
			if gap == 1:
				break
			gap = math.ceil(gap / 2)


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr = arr1 + arr2
		arr.sort()
		for i in range(len(arr1)):
			arr1[i] = arr[i]
		for i in range(len(arr2)):
			arr2[i] = arr[len(arr1) + i]
		return (arr1, arr2)


class Solution:

	def swapIfGreater(self, arr1, arr2, ind1, ind2):
		if arr1[ind1] > arr2[ind2]:
			(arr1[ind1], arr2[ind2]) = (arr2[ind2], arr1[ind1])

	def merge(self, arr1, arr2, n, m):
		len = n + m
		gap = len // 2 + len % 2
		while gap > 0:
			left = 0
			right = left + gap
			while right < len:
				if left < n and right >= n:
					self.swapIfGreater(arr1, arr2, left, right - n)
				elif left >= n:
					self.swapIfGreater(arr2, arr2, left - n, right - n)
				else:
					self.swapIfGreater(arr1, arr1, left, right)
				left += 1
				right += 1
			if gap == 1:
				break
			gap = gap // 2 + gap % 2


class Solution:

	def merge(self, arr1, arr2, n, m):
		arr3 = [0] * (n + m)
		left = 0
		right = 0
		index = 0
		while left < n and right < m:
			if arr1[left] <= arr2[right]:
				arr3[index] = arr1[left]
				left += 1
				index += 1
			else:
				arr3[index] = arr2[right]
				right += 1
				index += 1
		while left < n:
			arr3[index] = arr1[left]
			left += 1
			index += 1
		while right < m:
			arr3[index] = arr2[right]
			right += 1
			index += 1
		for i in range(n + m):
			if i < n:
				arr1[i] = arr3[i]
			else:
				arr2[i - n] = arr3[i]


class Solution:

	def merge(self, arr1, arr2, n, m):
		i = 0
		j = 0
		while i < len(arr1):
			if len(arr2) == 0:
				break
			while len(arr2) > 0 and i < len(arr1) and (arr2[j] < arr1[i]):
				p = arr2.pop(j)
				arr1.insert(i, p)
				i += 1
			i += 1
		arr1 = arr1[:n]
		arr2 = arr1[n:].extend(arr2)
		return (arr1, arr2)


class Solution:

	def merge(self, a, b, n, m):
		x = []
		x = a + b
		x.sort()
		for i in range(n):
			a[i] = x[0]
			x.pop(0)
		for i in range(m):
			b[i] = x[0]
			x.pop(0)
		return (a, b)


class Solution(object):

	def merge1(self, nums1, nums2, n, m):
		result = [-1] * (n + m)
		placement = index1 = index2 = 0
		while index1 < n and index2 < m:
			if nums1[index1] <= nums2[index2]:
				result[placement] = nums1[index1]
				index1 += 1
			else:
				result[placement] = nums2[index2]
				index2 += 1
			placement += 1
		while index1 < n:
			result[placement] = nums1[index1]
			index1 += 1
			placement += 1
		while index2 < m:
			result[placement] = nums2[index2]
			index2 += 1
			placement += 1
		for (index, num) in enumerate(result):
			if index < n:
				nums1[index] = result[index]
			else:
				nums2[index - n] = result[index]
		return nums1 + nums2

	def merge(self, nums1, nums2, n, m):
		(left, right) = (n - 1, 0)
		while 0 <= left and right < m and (nums1[left] > nums2[right]):
			(nums1[left], nums2[right]) = (nums2[right], nums1[left])
			left -= 1
			right += 1
		nums1.sort()
		nums2.sort()
		return nums1 + nums2


class Solution:

	def merge(self, arr1, arr2, n, m):
		new_arr = arr1 + arr2
		new_arr.sort()
		for i in range(n):
			arr1[i] = new_arr[i]
		for i in range(n, n + m):
			arr2[i - (n + m)] = new_arr[i]


class Solution:

	def merge(self, arr1, arr2, n, m):
		for ele in arr2:
			arr1.append(ele)
		arr1.sort()
		for i in range(m):
			arr2[i] = arr1[i + n]
		for i in range(m):
			arr1.pop()
		return (arr1, arr2)


class Solution:

	def merge(self, arr1, arr2, n, m):
		p = arr1 + arr2
		p.sort()
		q = p[0:n]
		r = p[n:]
		for i in range(len(arr1)):
			arr1[i] = q[i]
		for j in range(len(arr2)):
			arr2[j] = r[j]
		return arr1
		return arr2


import math

class Solution:

	def next_gap(self, gap):
		if gap <= 1:
			return 0
		return int(math.ceil(float(gap) / 2))

	def merge(self, arr1, arr2, n, m):
		gap = int(math.ceil(float(n + m) / 2))
		while gap > 0:
			i = 0
			while i + gap < n:
				if arr1[i] > arr1[i + gap]:
					(arr1[i], arr1[i + gap]) = (arr1[i + gap], arr1[i])
				i += 1
			j = gap - n if gap > n else 0
			while i < n and j < m:
				if arr1[i] > arr2[j]:
					(arr1[i], arr2[j]) = (arr2[j], arr1[i])
				i += 1
				j += 1
			if j < m:
				j = 0
				while j + gap < m:
					if arr2[j] > arr2[j + gap]:
						(arr2[j], arr2[j + gap]) = (arr2[j + gap], arr2[j])
					j += 1
			gap = self.next_gap(gap)


class Solution:

	class heap:

		def __init__(self, arr):
			self.arr = arr
			self.n = len(arr)
			for i in range(self.n // 2, -1, -1):
				self.heapify(i)

		def heapify(self, i):
			largest = i
			left = 2 * i + 1
			right = 2 * i + 2
			if left < self.n and self.arr[i] < self.arr[left]:
				largest = left
			if right < self.n and self.arr[largest] < self.arr[right]:
				largest = right
			if largest != i:
				(self.arr[i], self.arr[largest]) = (self.arr[largest], self.arr[i])
				self.heapify(largest)

		def pop(self):
			(self.arr[0], self.arr[self.n - 1]) = (self.arr[self.n - 1], self.arr[0])
			self.n -= 1
			self.heapify(0)

	def merge(self, arr1, arr2, n, m):
		hs1 = self.heap(arr1)
		hs2 = self.heap(arr2)
		while m > 0:
			if arr2[0] >= arr1[0]:
				hs2.pop()
			else:
				(arr1[0], arr2[0]) = (arr2[0], arr1[0])
				hs2.pop()
				hs1.heapify(0)
			m -= 1
		while n > 0:
			hs1.pop()
			n -= 1


class Solution:

	class Max_Heap:

		def __init__(self, Arr):
			self.Arr = Arr
			self.Len = len(Arr)
			for i in range(self.Len // 2, -1, -1):
				self.Heapify(i)

		def Heapify(self, index):
			l = 2 * index + 1
			r = l + 1
			K = index
			if r < self.Len:
				if self.Arr[l] > self.Arr[r]:
					K = l
				else:
					K = r
			elif l < self.Len:
				K = l
			while self.Arr[K] > self.Arr[index]:
				(self.Arr[K], self.Arr[index]) = (self.Arr[index], self.Arr[K])
				index = K
				l = 2 * index + 1
				r = l + 1
				if r < self.Len:
					if self.Arr[l] > self.Arr[r]:
						K = l
					else:
						K = r
				elif l < self.Len:
					K = l

		def Pop_Key(self, index):
			(self.Arr[self.Len - 1], self.Arr[index]) = (self.Arr[index], self.Arr[self.Len - 1])
			self.Len -= 1
			if self.Len:
				self.Heapify(index)

	def merge(self, arr1, arr2, n, m):
		(mh1, mh2) = (self.Max_Heap(arr1), self.Max_Heap(arr2))
		while mh2.Len:
			if arr1[0] > arr2[0]:
				(arr1[0], arr2[0]) = (arr2[0], arr1[0])
				mh1.Heapify(0)
			mh2.Pop_Key(0)
		while mh1.Len:
			mh1.Pop_Key(0)