Merge without extra space

• Merge two sorted arrays with O(1) extra space usinginsertion_sort with Simultaneous Merge

Merge two sorted arrays with O(1) extra space using Euclidean Division Lemma

# Python3 program to merge two sorted arrays without using extra space
 
 
def merge(arr1, arr2, n, m):
	# three pointers to iterate
	i = 0
	j = 0
	k = 0
	# for euclid's division lemma
	x = 10e7 + 1
	# in this loop we are rearranging the elements of arr1
	while i < n and (j < n and k < m):
		# if both arr1 and arr2 elements are modified
		if arr1[j] >= x and arr2[k] >= x:
			if arr1[j] % x <= arr2[k] % x:
				arr1[i] += (arr1[j] % x) * x
				j += 1
			else:
				arr1[i] += (arr2[k] % x) * x
				k += 1
		# if only arr1 elements are modified
		elif arr1[j] >= x:
			if arr1[j] % x <= arr2[k]:
				arr1[i] += (arr1[j] % x) * x
				j += 1
			else:
				arr1[i] += (arr2[k] % x) * x
				k += 1
		# if only arr2 elements are modified
		elif arr2[k] >= x:
			if arr1[j] <= arr2[k] % x:
				arr1[i] += (arr1[j] % x) * x
				j += 1
			else:
				arr1[i] += (arr2[k] % x) * x
				k += 1
		# if none elements are modified
		else:
			if arr1[j] <= arr2[k]:
				arr1[i] += (arr1[j] % x) * x
				j += 1
			else:
				arr1[i] += (arr2[k] % x) * x
				k += 1
		i += 1
 
	# we can copy the elements directly as the other array
	# is exchausted
	while j < n and i < n:
		arr1[i] += (arr1[j] % x) * x
		i += 1
		j += 1
	while k < m and i < n:
		arr1[i] += (arr2[k] % x) * x
		i += 1
		k += 1
	# we need to reset i
	i = 0
 
	# in this loop we are rearranging the elements of arr2
	while i < m and (j < n and k < m):
		# if both arr1 and arr2 elements are modified
		if arr1[j] >= x and arr2[k] >= x:
			if arr1[j] % x <= arr2[k] % x:
				arr2[i] += (arr1[j] % x) * x
				j += 1
 
			else:
				arr2[i] += (arr2[k] % x) * x
				k += 1
 
		# if only arr1 elements are modified
		elif arr1[j] >= x:
			if arr1[j] % x <= arr2[k]:
				arr2[i] += (arr1[j] % x) * x
				j += 1
 
			else:
				arr2[i] += (arr2[k] % x) * x
				k += 1
 
		# if only arr2 elements are modified
		elif arr2[k] >= x:
			if arr1[j] <= arr2[k] % x:
				arr2[i] += (arr1[j] % x) * x
				j += 1
 
			else:
				arr2[i] += (arr2[k] % x) * x
				k += 1
 
		else:
			# if none elements are modified
			if arr1[j] <= arr2[k]:
				arr2[i] += (arr1[j] % x) * x
				j += 1
 
			else:
				arr2[i] += (arr2[k] % x) * x
				k += 1
 
		i += 1
	# we can copy the elements directly as the other array
	# is exhausted
	while j < n and i < m:
		arr2[i] += (arr1[j] % x) * x
		i += 1
		j += 1
 
	while k < m and i < m:
		arr2[i] += (arr2[k] % x) * x
		i += 1
		k += 1
 
	# we need to reset i
	i = 0
	# we need to divide the whole arr1 by x
	while i < n:
		arr1[i] /= x
		i += 1
 
	# we need to reset i
	i = 0
	# we need to divide the whole arr2 by x
	while i < m:
		arr2[i] /= x
		i += 1
 
# Driver program
 
 
ar1 = [1, 5, 9, 10, 15, 20]
ar2 = [2, 3, 8, 13]
m = len(ar1)
n = len(ar2)
 
merge(ar1, ar2, m, n)
 
print("After Merging \nFirst Array:", end=" ")
for i in range(m):
	print(int(ar1[i]), end=" ")
print("\nSecond Array:", end=" ")
for i in range(n):
	print(int(ar2[i]), end=" ")