Given an integer array of which both the first halve and second halve are sorted. The task is to merge these two sorted halves of the array into a single sorted array.
Note: The two halves can be of arbitrary sizes (i.e. if first halve of size k then the second halve is of size N-k where 0<=k<=N).
Example 1:
Input:
N = 6
arr[] = {2 3 8 -1 7 10}
Output: -1 2 3 7 8 10 
Explanation: {2 3 8} and {-1 7 10} are sorted 
in the original array. The overall sorted 
version is {-1 2 3 7 8 10}
Example 2:
Input:
N = 5
arr[] = {-4 6 9 -1 3}
Output: -4 -1 3 6 9 
Explanation: {-4 -1} and {3 6 9} are sorted 
in the original array. The overall sorted 
version is {-4 -1 3 6 9}
Your Task:
You don't need to read input or print anything. Your task is to complete the function sortHalves () which takes the array arr[] and its size n as inputs and modifies the array such that it gets sorted completely.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
Constraints:
1 <= N <= 10^{6}

Difficulty: EASY
Tags: Sorting

Amortized analysis
Skill types: Sorting

Amortized analysis
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).

Starter code:
#User function Template for python3

class Solution:
    def sortHalves (self, arr, n):
        # your code here

Solutions:
class Solution:

	def sortHalves(self, arr, n):
		arr.sort()
		return arr


class Solution:

	def sortHalves(self, arr, n):
		return sorted(arr)


class Solution:

	def sortHalves(self, arr, n):
		for i in range(n - 1):
			if arr[i + 1] < arr[i]:
				left_arr = arr[:i + 1]
				right_arr = arr[i + 1:]
				break
		else:
			left_arr = arr[:n // 2]
			right_arr = arr[n // 2:]
		i = 0
		j = 0
		k = 0
		while i < len(left_arr) and j < len(right_arr):
			if left_arr[i] < right_arr[j]:
				arr[k] = left_arr[i]
				i += 1
			else:
				arr[k] = right_arr[j]
				j += 1
			k += 1
		while i < len(left_arr):
			arr[k] = left_arr[i]
			i += 1
			k += 1
		while j < len(right_arr):
			arr[k] = right_arr[j]
			j += 1
			k += 1
		return arr


class Solution:

	def sortHalves(self, arr, n):
		if n == 1:
			return arr
		if len(arr) > 1:
			cnt = 0
			temp = arr[0]
			mid = 0
			for i in arr:
				if i < temp:
					mid = cnt
					break
				temp = i
				cnt += 1
			left_arr = arr[:mid]
			right_arr = arr[mid:]
		i = 0
		j = 0
		k = 0
		while i < len(left_arr) and j < len(right_arr):
			if left_arr[i] < right_arr[j]:
				arr[k] = left_arr[i]
				i += 1
			else:
				arr[k] = right_arr[j]
				j += 1
			k += 1
		while i < len(left_arr):
			arr[k] = left_arr[i]
			i += 1
			k += 1
		while j < len(right_arr):
			arr[k] = right_arr[j]
			j += 1
			k += 1
		return arr


class Solution:

	def sortHalves(self, arr, n):
		half_i = 0
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				half_i = i + 1
				break
		temp = [0 for i in range(n)]
		itr = 0
		i = 0
		j = half_i
		while i < half_i or j < n:
			if i >= half_i:
				temp[itr] = arr[j]
				itr += 1
				j += 1
			elif j >= n:
				temp[itr] = arr[i]
				itr += 1
				i += 1
			elif arr[i] < arr[j]:
				temp[itr] = arr[i]
				itr += 1
				i += 1
			else:
				temp[itr] = arr[j]
				itr += 1
				j += 1
		i = 0
		while i < n:
			arr[i] = temp[i]
			i += 1


class Solution:

	def sortHalves(self, arr, n):
		if len(arr) > 1:
			cnt = 0
			temp = arr[0]
			mid = 0
			for i in arr:
				if i < temp:
					mid = cnt
					break
				temp = i
				cnt += 1
			L = arr[:mid]
			R = arr[mid:]
			i = j = k = 0
			while i < len(L) and j < len(R):
				if L[i] <= R[j]:
					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


class Solution:

	def sortHalves(self, arr, n):
		arr1 = sorted(arr)
		j = 0
		for i in arr1:
			arr[j] = i
			j += 1


class Solution:

	def sortHalves(self, arr, n):
		a = sorted(arr)
		for i in range(n):
			arr[i] = a[i]
		return arr


class Solution:

	def sortHalves(self, arr, n):
		for i in range(n):
			if i == n - 1 or arr[i + 1] < arr[i]:
				break
		m = i
		l = []
		r = []
		for i in range(m + 1):
			l.append(arr[i])
		for i in range(m + 1, n):
			r.append(arr[i])
		i = 0
		j = 0
		k = 0
		while i < len(l) and j < len(r):
			if l[i] > r[j]:
				arr[k] = r[j]
				j += 1
			else:
				arr[k] = l[i]
				i += 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 arr


class Solution:

	def sortHalves(self, arr, n):
		arr.sort()
		K = arr[:n // 2]
		L = arr[n // 2:]
		M = []
		i = j = 0
		while i < n // 2 and j < n // 2:
			if K[i] < L[j]:
				M.append(K[i])
				i += 1
			else:
				M.append(L[j])
				j += 1
		return M


class Solution:

	def sortHalves(self, arr, n):
		i = 0
		pt = 0
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				pt = i + 1
				break
		i = 0
		j = pt
		res = [0] * n
		k = 0
		while i < pt and j < n:
			if arr[i] < arr[j]:
				res[k] = arr[i]
				i += 1
			else:
				res[k] = arr[j]
				j += 1
			k += 1
		while i < pt:
			res[k] = arr[i]
			i += 1
			k += 1
		while j < n:
			res[k] = arr[j]
			j += 1
			k += 1
		for i in range(n):
			arr[i] = res[i]


class Solution:

	def sortHalves(self, arr, n):
		t = len(arr) // 2
		if len(arr) % 2 == 0:
			a = arr[:t]
			b = arr[t:]
		else:
			a = arr[:t]
			b = arr[t:]
		v = a + b
		v = sorted(v)
		for i in range(len(v)):
			arr[i] = v[i]


class Solution:

	def sortHalves(self, arr, n):
		pivot = 0
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				pivot = i + 1
		L = arr[:pivot]
		R = arr[pivot:]
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
				k += 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 arr


class Solution:

	def sortHalves(self, arr, n):
		if n > 1:
			L = []
			for i in range(0, n - 1):
				if arr[i] > arr[i + 1]:
					L.append(arr[i])
					break
				else:
					L.append(arr[i])
			R = arr[len(L):]
			i = 0
			k = 0
			j = 0
			sizeL = len(L)
			sizeR = len(R)
			while i < sizeL and j < sizeR:
				if L[i] < R[j]:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
				k += 1
			while i < sizeL:
				arr[k] = L[i]
				i += 1
				k += 1
			while j < sizeR:
				arr[k] = R[j]
				j += 1
				k += 1


import math

class Solution:

	def sortHalves(self, arr, n):
		mid = 0
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				mid = i + 1
				break
		n1 = mid
		n2 = n - mid
		temp1 = [0] * n1
		temp2 = [0] * n2
		for i in range(n1):
			temp1[i] = arr[i]
		for i in range(n2):
			temp2[i] = arr[mid + i]
		i = 0
		j = 0
		k = 0
		while i < n1 and j < n2:
			if temp1[i] < temp2[j]:
				arr[k] = temp1[i]
				i += 1
			else:
				arr[k] = temp2[j]
				j += 1
			k += 1
		while i < n1:
			arr[k] = temp1[i]
			i += 1
			k += 1
		while j < n2:
			arr[k] = temp2[j]
			j += 1
			k += 1
		return arr


import math

class Solution:

	def sortHalves(self, A, n):
		half_i = 0
		temp = [0 for i in range(n)]
		for i in range(n - 1):
			if A[i] > A[i + 1]:
				half_i = i + 1
				break
		if half_i == 0:
			return
		i = 0
		j = half_i
		k = 0
		while i < half_i and j < n:
			if A[i] < A[j]:
				temp[k] = A[i]
				k += 1
				i += 1
			else:
				temp[k] = A[j]
				k += 1
				j += 1
		while i < half_i:
			temp[k] = A[i]
			k += 1
			i += 1
		while j < n:
			temp[k] = A[j]
			k += 1
			j += 1
		for i in range(n):
			A[i] = temp[i]
		return A


class Solution:

	def sortHalves(self, arr, n):
		return arr.sort()
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	ob.sortHalves(arr, n)
	for i in range(n):
		print(arr[i], end=' ')
	print()


class Solution:

	def sortHalves(self, arr, n):
		res = []
		i = 0
		for i in range(0, n - 1):
			if arr[i] > arr[i + 1]:
				break
		j = i + 1
		k = j
		i = 0
		while i < k and j < n:
			if arr[i] < arr[j]:
				res.append(arr[i])
				i += 1
			else:
				res.append(arr[j])
				j += 1
		while i < k:
			res.append(arr[i])
			i += 1
		while j < n:
			res.append(arr[j])
			j += 1
		arr.clear()
		for i in res:
			arr.append(i)
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ob = Solution()
	ob.sortHalves(arr, n)
	for i in range(n):
		print(arr[i], end=' ')
	print()


class Solution:

	def sortHalves(self, arr, n):
		arr.sort()

	def inv(self, arr, i, f):
		while i < f:
			(arr[i], arr[f]) = (arr[f], arr[i])
			i += 1
			f -= 1


class Solution:

	def sortHalves(self, arr, n):
		l = []
		i = 0
		j = n - 1
		while i < n - 1:
			if arr[i] > arr[i + 1]:
				j = i + 1
				break
			i += 1
		p = 0
		q = 0
		while p < i + 1 and j < n:
			if arr[p] < arr[j]:
				l.append(arr[p])
				p += 1
			else:
				l.append(arr[j])
				j += 1
		while p < i + 1:
			l.append(arr[p])
			p += 1
		while j < n:
			l.append(arr[j])
			j += 1
		for i in range(0, n):
			arr[i] = l[i]


class Solution:

	def sortHalves(self, arr, n):
		if len(arr) < 1:
			return
		for i in range(len(arr)):
			if arr[i - 1] > arr[i]:
				left = arr[:i]
				right = arr[i:]
				i = k = 0
				j = 0
				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
		return arr


class Solution:

	def sortHalves(self, a, n):
		return a.sort()


class Solution:

	def sortHalves(self, arr, n):
		x = 0
		arr_middle = -1
		while x < n:
			if x + 1 == n:
				return
			if arr[x] > arr[x + 1]:
				arr_middle = x + 1
				break
			x += 1
		arr1_index = 0
		arr2_index = arr_middle
		final_arr = []
		change = 0
		while arr1_index < arr_middle and arr2_index < n:
			if arr[arr1_index] < arr[arr2_index]:
				final_arr.append(arr[arr1_index])
				arr1_index += 1
			else:
				final_arr.append(arr[arr2_index])
				arr2_index += 1
		if arr1_index < arr_middle:
			final_arr.extend(arr[arr1_index:arr_middle])
		if arr2_index < n:
			final_arr.extend(arr[arr2_index:])
		for i in range(n):
			arr[i] = final_arr[i]


class Solution:

	def sortHalves(self, arr, n):
		j = 0
		for i in range(1, n):
			if arr[i - 1] > arr[i]:
				j = i
				break
		i_limit = j
		i = 0
		a = [0] * n
		ind = 0
		while i < i_limit and j < n:
			if arr[i] < arr[j]:
				a[ind] = arr[i]
				i += 1
			else:
				a[ind] = arr[j]
				j += 1
			ind += 1
		while i < i_limit:
			a[ind] = arr[i]
			ind += 1
			i += 1
		while j < n:
			a[ind] = arr[j]
			j += 1
			ind += 1
		for i in range(n):
			arr[i] = a[i]


class Solution:

	def sortHalves(self, arr, n):
		pivot = -1
		for i in range(1, n - 1):
			if arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
				pivot = i
				break
		return arr.sort()


class Solution:

	def qs(self, arr):
		if len(arr) <= 1:
			return arr
		vl = arr.pop()
		ls = []
		gr = []
		for i in range(len(arr)):
			if vl > arr[i]:
				ls.append(arr[i])
			else:
				gr.append(arr[i])
		arr[:len(arr)] = self.qs(ls) + [vl] + self.qs(gr)
		return arr

	def sortHalves(self, arr, n):
		return arr.sort()


class Solution:

	def sortHalves(self, arr, n):
		first = 0
		second = 0
		arr1 = []
		arr2 = []
		for i in range(1, n):
			if arr[i - 1] > arr[i]:
				second = i
				break
		for i in range(first, second):
			arr1.append(arr[i])
		for i in range(second, n):
			arr2.append(arr[i])
		i = 0
		j = 0
		k = 0
		while i < len(arr1) and j < len(arr2):
			if arr1[i] > arr2[j]:
				arr[k] = arr2[j]
				j = j + 1
			else:
				arr[k] = arr1[i]
				i = i + 1
			k = k + 1
		while i < len(arr1):
			arr[k] = arr1[i]
			i = i + 1
			k = k + 1
		while j < len(arr2):
			arr[k] = arr2[j]
			j = j + 1
			k = k + 1


class Solution:

	def sortHalves(self, arr, n):
		pivot = 0
		for i in range(1, n):
			if arr[i] < arr[i - 1]:
				pivot = i
				break
		i = 0
		j = pivot
		k = 0
		K = [0] * n
		while i < pivot and j < n:
			if arr[i] <= arr[j]:
				K[k] = arr[i]
				i += 1
			else:
				K[k] = arr[j]
				j += 1
			k += 1
		while i < pivot:
			K[k] = arr[i]
			i += 1
			k += 1
		while j < n:
			K[k] = arr[j]
			j += 1
			k += 1
		for i in range(n):
			arr[i] = K[i]