Given an array arr of n integers, sort the first half of the array in ascending order and second half in descending order.
Example 1:
Input:
n = 4
arr[] = {10, 20, 30, 40}
Output: 10 20 40 30
Example 2:
Input:
n = 9
arr[] = {5, 4, 6, 2, 1, 3, 8, 9, 7}
Output: 2 4 5 6 9 8 7 3 1
Your Task:
You don't need to read input or print anything. Your task is to complete the function customSort() which takes the array of integers arr and n as parameters and returns void. You need to change the array itself.
Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(1)
Constraints: 
1 <= n <= 10^{5}
1 <= arr[i] <= 10^{6}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3




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

Solutions:
class Solution:

	def customSort(self, arr, n):
		i = n // 2
		arr[:i] = sorted(arr[:i])
		arr[i:] = sorted(arr[i:], reverse=True)
		return arr


class Solution:

	def customSort(self, arr, n):
		arr[0:int(n / 2)] = sorted(arr[0:int(n / 2)])
		arr[int(n / 2):] = list(reversed(sorted(arr[int(n / 2):])))


class Solution:

	def customSort(self, arr, n):
		left = arr[:n // 2]
		right = arr[n // 2:]
		left.sort()
		right.sort(reverse=True)
		left = left + right
		for i in range(n):
			arr[i] = left[i]


class Solution:

	def customSort(self, arr, n):
		mid = n // 2
		b = arr[:mid]
		c = arr[mid:]
		b.sort()
		c.sort(reverse=True)
		d = b + c
		arr[:] = d[:]
		return arr


class Solution:

	def customSort(self, arr, n):
		p = arr[:n // 2]
		q = arr[n // 2:]
		p.sort()
		q.sort()
		q.reverse()
		a = p + q
		arr[:] = a[:]


class Solution:

	def customSort(self, arr, n):
		li = []
		li2 = []
		for i in range(n // 2):
			li.append(arr[i])
		li = sorted(li)
		for j in range(n // 2, n):
			li2.append(arr[j])
		li2.sort(reverse=True)
		for i in range(len(li2)):
			li.append(li2[i])
		return li


class Solution:

	def customSort(self, arr, n):
		op = arr[:n // 2]
		lp = arr[n // 2:]
		op.sort()
		lp.sort(reverse=True)
		d = op + lp
		arr[:] = d[:]
		return arr


class Solution:

	def customSort(self, arr, n):
		m = n // 2
		a = arr[:m]
		b = arr[m:]
		a.sort()
		b.sort(reverse=True)
		a.extend(b)
		for i in range(n):
			arr[i] = a[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		i = n // 2
		brr = sorted(arr[:i]) + sorted(arr[i:], reverse=True)
		for i in range(n):
			arr[i] = brr[i]
		return


class Solution:

	def customSort(self, arr, n):
		arr1 = []
		arr2 = []
		i = 0
		while i < n:
			if i < n // 2:
				arr1.append(arr[i])
			else:
				arr2.append(arr[i])
			i += 1
		arr1.sort()
		arr2.sort(reverse=True)
		for i in range(len(arr1)):
			arr[i] = arr1[i]
		for i in range(len(arr2)):
			arr[i + len(arr1)] = arr2[i]


class Solution:

	def customSort(self, arr, n):
		dupli = arr.copy()
		(left, right) = (arr[:n // 2], arr[n // 2:])
		(left.sort(), right.sort(reverse=True))
		arr.clear()
		(arr.extend(left), arr.extend(right))
		return arr


class Solution:

	def customSort(self, arr, n):
		a = arr[:n // 2]
		b = arr[n // 2:]
		a.sort()
		b.sort(reverse=True)
		arr[:] = a + b


class Solution:

	def customSort(self, arr, n):
		arr[:n // 2] = sorted(arr[:n // 2])
		arr[n // 2:] = sorted(arr[n // 2:], reverse=True)


class Solution:

	def customSort(self, arr, n):
		a = arr[:n // 2]
		b = arr[n // 2:]
		a.sort()
		b.sort(reverse=True)
		c = a + b
		for i in range(len(c)):
			arr[i] = c[i]


class Solution:

	def customSort(self, arr, n):
		n = n // 2
		fh = arr[:n]
		sh = arr[n:]
		fh.sort()
		sh.sort(reverse=True)
		res = fh + sh
		arr[:] = res[:]
		return res


class Solution:

	def customSort(self, arr, n):
		a = n // 2
		arr[0:a] = sorted(arr[0:a])
		arr[a:n] = sorted(arr[a:n], reverse=True)
		return arr


class Solution:

	def customSort(self, arr, n):
		b = []
		c = []
		m = n // 2
		for i in range(0, m):
			b.append(arr[i])
		for i in range(m, n):
			c.append(arr[i])
		b.sort()
		c.sort(reverse=True)
		d = b + c
		for i in range(n):
			arr[i] = d[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		t = n // 2
		l = arr[:t]
		l.sort()
		for i in range(0, t):
			arr[i] = l[i]
		h = arr[t:]
		h.sort(reverse=True)
		for i in h:
			arr[t] = i
			t = t + 1


class Solution:

	def customSort(self, arr, n):
		l = n // 2
		arr1 = sorted(arr[0:l])
		arr2 = sorted(arr[l:n], reverse=True)
		arr3 = arr1 + arr2
		arr[:] = arr3[:]


class Solution:

	def customSort(self, arr, n):
		from math import floor
		m = floor(n / 2)
		l = arr[0:m]
		l.sort()
		r = arr[m:n]
		r.sort(reverse=True)
		a1 = l + r
		for (i, v) in enumerate(a1):
			arr[i] = v


class Solution:

	def customSort(self, arr, n):
		l1 = arr[:n // 2]
		l2 = arr[n // 2:]
		l1.sort()
		l2.sort(reverse=True)
		arr.clear()
		l3 = l1 + l2
		for i in l3:
			arr.append(i)


class Solution:

	def customSort(self, arr, n):
		half = n // 2
		list1 = arr[:half]
		list2 = arr[half:]
		list1.sort()
		list2.sort(reverse=True)


class Solution:

	def customSort(self, arr, n):
		a1 = arr[:n // 2]
		a2 = arr[n // 2:]
		a1.sort()
		a2.sort(reverse=True)
		arr[:] = a1[:] + a2[:]


class Solution:

	def customSort(self, arr, n):
		b = arr[0:n // 2]
		c = arr[n // 2:n]
		b.sort()
		c.sort(reverse=True)
		b.extend(c)
		for i in range(0, n):
			arr[i] = b[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		if n % 2 == 0:
			l = arr[:n // 2]
			l1 = arr[n // 2:]
			l.sort()
			l1.sort()
			l1 = l1[::-1]
			l2 = l + l1
			for i in range(n):
				arr[i] = l2[i]
		else:
			l = arr[:n // 2]
			l1 = arr[n // 2:]
			l.sort()
			l1.sort()
			l1 = l1[::-1]
			l2 = l + l1
			for i in range(n):
				arr[i] = l2[i]


class Solution:

	def customSort(self, arr, n):
		l = sorted(arr[:n // 2])
		r = sorted(arr[n // 2:], reverse=True)
		new = l + r
		for i in range(len(new)):
			arr[i] = new[i]


class Solution:

	def customSort(self, arr, n):
		middle = n // 2
		a = arr[:middle]
		b = arr[middle:]
		a.sort()
		b.sort(reverse=True)
		c = a + b
		arr[:] = c[:]
		return arr


class Solution:

	def customSort(self, arr, n):
		g = [arr[i] for i in range(0, n // 2)]
		h = [arr[i] for i in range(n // 2, n)]
		g.sort()
		h.sort()
		j = h[::-1]
		arr[:] = g + j


class Solution:

	def customSort(self, arr, n):
		x = sorted(arr[:n // 2])
		y = sorted(arr[n // 2:])
		z = y[::-1]
		a = x + z
		for i in range(n):
			if arr[i] != a[i]:
				arr[i] = a[i]


class Solution:

	def customSort(self, arr, n):
		(brr, crr) = (arr[:n // 2], arr[n // 2:])
		brr.sort()
		crr.sort(reverse=True)
		arr.clear()
		krr = brr + crr
		arr[:] = krr[:]
		return arr


class Solution:

	def customSort(self, arr, n):
		k = arr[:n // 2].copy()
		j = arr[n // 2:n].copy()
		k.sort()
		j.sort()
		lis = []
		lis = k.copy()
		for i in j[::-1]:
			lis.append(i)
		for i in range(n):
			arr[i] = lis[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		a1 = arr[:n // 2]
		a2 = arr[n // 2:]
		a1.sort()
		a2.sort(reverse=True)
		arr.clear()
		arr.extend(a1)
		arr.extend(a2)
		return arr


class Solution:

	def customSort(self, arr, n):
		length = n // 2
		first_half = []
		second_half = []
		for i in range(length):
			first_half.append(arr[i])
		for j in range(length, n):
			second_half.append(arr[j])
		first_half.sort()
		second_half.sort(reverse=True)
		new_array = first_half + second_half
		arr.clear()
		for i in range(len(new_array)):
			arr.append(new_array[i])


class Solution:

	def customSort(self, arr, n):
		a = int(n / 2)
		b = arr[a:n]
		c = arr[0:a]
		b.sort(reverse=True)
		c.sort()
		d = c + b
		arr[:] = d


class Solution:

	def customSort(self, arr, n):
		index = len(arr) // 2
		arr[0:index] = sorted(arr[:index])
		arr[index:n] = sorted(arr[index:n], reverse=True)


class Solution:

	def customSort(self, arr, n):
		l = []
		k = []
		m = n // 2
		for i in range(0, m):
			l.append(arr[i])
		for j in range(m, n):
			k.append(arr[j])
		l.sort()
		k.sort(reverse=True)
		c = l + k
		for i in range(n):
			arr[i] = c[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		(a, b) = ([], [])
		for i in range(0, n // 2):
			a.append(arr[i])
		for i in range(n // 2, n):
			b.append(arr[i])
		a.sort()
		b.sort(reverse=True)
		arr[:] = a + b
		return arr


class Solution:

	def customSort(self, arr, n):
		mid = n // 2
		x = arr[:mid]
		y = arr[mid:]
		x.sort()
		y.sort(reverse=True)
		a = x + y
		for i in range(n):
			arr[i] = a[i]


class Solution:

	def customSort(self, arr, n):
		x = []
		y = []
		mid = n // 2
		for i in range(0, mid):
			x.append(arr[i])
		for i in range(mid, n):
			y.append(arr[i])
		x.sort()
		y.sort(reverse=True)
		l = x + y
		for i in range(n):
			arr[i] = l[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		mid = n // 2
		arr1 = arr[:mid]
		arr2 = arr[mid:]
		arr1.sort()
		arr2.sort(reverse=True)
		arr[:] = arr1 + arr2


class Solution:

	def customSort(self, arr, n):
		l = len(arr)
		a1 = arr[:l // 2]
		a2 = arr[l // 2:]
		a1 = sorted(a1)
		a2 = sorted(a2, reverse=True)
		a1.extend(a2)
		for x in range(n):
			arr[x] = str(a1[x])
		arr = ' '.join(arr)
		return arr


class Solution:

	def customSort(self, arr, n):
		mid = n // 2
		new_arr = arr[:mid]
		new_arr1 = arr[mid:]
		new_arr.sort()
		new_arr1.sort(reverse=True)
		count = 0
		for i in range(n):
			if i <= mid - 1:
				arr[i] = new_arr[i]
			else:
				arr[i] = new_arr1[count]
				count += 1
		return arr


class Solution:

	def customSort(self, arr, n):
		if n % 2 == 0:
			mid = n // 2
		else:
			mid = (n - 1) // 2
		first = arr[:mid]
		second = arr[mid:]
		first.sort()
		second.sort(reverse=True)
		lst = first + second
		for i in range(n):
			arr[i] = lst[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		fh = arr[:n // 2]
		sh = arr[n // 2:]
		fh.sort()
		sh.sort(reverse=True)
		nar = fh + sh
		for i in range(n):
			arr[i] = nar[i]


class Solution:

	def customSort(self, arr, n):
		if n % 2 == 0:
			l = int(n / 2)
		else:
			l = n // 2
		a1 = arr[:l]
		a2 = arr[l:n]
		a1.sort()
		a2.sort(reverse=True)
		arr[:l] = a1
		arr[l:n] = a2
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		Solution().customSort(arr, n)
		for x in arr:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def customSort(self, arr, n):
		x = list(())
		y = list(())
		for i in range(int(n // 2)):
			x.append(arr[i])
		for i in range(n // 2, n):
			y.append(arr[i])
		x.sort()
		y.sort(reverse=True)
		p = x + y
		for i in range(n):
			arr[i] = p[i]
		return arr
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		Solution().customSort(arr, n)
		for x in arr:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def customSort(self, arr, n):
		i = n // 2
		arr[0:i] = sorted(arr[0:i])
		arr[i:n] = sorted(arr[i:n], reverse=True)
		return arr
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		Solution().customSort(arr, n)
		for x in arr:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def customSort(self, arr, n):
		b = arr[:n // 2]
		c = arr[n // 2:]
		b.sort()
		c.sort()
		c = c[::-1]
		b.extend(c)
		for i in range(n):
			arr[i] = b[i]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		Solution().customSort(arr, n)
		for x in arr:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def customSort(self, arr, n):
		first = []
		second = []
		for itr in range(n // 2):
			first.append(arr[itr])
		for itr in range(n // 2, n):
			second.append(arr[itr])
		first.sort()
		second.sort(reverse=True)
		for itr in range(n // 2):
			arr[itr] = first[itr]
		for itr in range(n // 2, n):
			arr[itr] = second[itr - n // 2]
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		Solution().customSort(arr, n)
		for x in arr:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def customSort(self, arr, n):
		b = []
		c = []
		m = n // 2
		for i in range(0, m):
			b.append(arr[i])
		for i in range(m, n):
			c.append(arr[i])
		b.sort()
		c.sort(reverse=True)
		d = b + c
		for i in range(n):
			arr[i] = d[i]
		return arr
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		Solution().customSort(arr, n)
		for x in arr:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def customSort(self, arr, n):
		x = n // 2
		arr1 = []
		arr2 = []
		for i in range(0, x):
			arr1.append(arr[i])
		for i in range(x, n):
			arr2.append(arr[i])
		arr1.sort()
		arr2.sort(reverse=True)
		for i in arr2:
			arr1.append(i)
		for i in range(n):
			arr[i] = arr1[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		if n == 1:
			return arr
		mid = int(n / 2)
		arr1 = arr[0:mid]
		arr2 = arr[mid:]
		arr1.sort()
		arr2.sort(reverse=True)
		i = 0
		for i in range(0, len(arr1)):
			arr[i] = arr1[i]
		for j in range(0, len(arr2)):
			i += 1
			arr[i] = arr2[j]
		return arr


class Solution:

	def customSort(self, arr, n):
		arr1 = arr[:n // 2]
		arr2 = arr[n // 2:]
		arr1.sort()
		arr2.sort(reverse=True)
		x = n // 2
		i = 0
		j = 0
		k = 0
		while i < n:
			if i < x:
				arr[i] = arr1[j]
				j += 1
			else:
				arr[i] = arr2[k]
				k += 1
			i += 1


class Solution:

	def customSort(self, arr, n):
		k = n // 2
		l = sorted(arr[:k]) + sorted(arr[k:], reverse=True)
		arr.clear()
		arr = l
		for i in arr:
			print(i, end=' ')


class Solution:

	def customSort(self, arr, n):
		li = [0] * (n // 2)
		li2 = [0] * (n - n // 2)
		for i in range(n // 2):
			li[i] = arr[i]
		for i in range(n // 2, n):
			li2[i - n // 2] = arr[i]
		li.sort()
		li2.sort(reverse=True)
		for i in range(n):
			if i < n // 2:
				arr[i] = li[i]
			else:
				arr[i] = li2[i - n // 2]
		return arr


class Solution:

	def customSort(self, arr, n):
		half1 = arr[:n // 2]
		half2 = arr[n // 2:]
		half1.sort()
		half2.sort(reverse=True)
		s = half1 + half2
		for i in range(len(arr)):
			arr[i] = s[i]


class Solution:

	def customSort(self, arr, n):
		arrA = arr[:n // 2]
		arrA.sort()
		arrD = arr[n // 2:]
		arrD.sort(reverse=True)
		arr_sorted = arrA + arrD
		for i in range(len(arr)):
			arr[i] = arr_sorted[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		a1 = arr[:n // 2]
		a2 = arr[n // 2:]
		a1.sort()
		a2.sort(reverse=True)
		a1.extend(a2)
		for i in range(n):
			arr[i] = a1[i]


class Solution:

	def customSort(self, arr, n):
		first = []
		odd = []
		for i in range(0, n // 2):
			first.append(arr[i])
		for i in range(n // 2, len(arr)):
			odd.append(arr[i])
		first.sort()
		odd.sort(reverse=True)
		for i in odd:
			first.append(i)
		for i in range(len(arr)):
			arr[i] = first[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		n = n // 2
		last = arr[n:]
		first = arr[:n]
		first.sort()
		last.sort()
		last = last[::-1]
		first = first + last
		for i in first:
			print(i, end=' ')
		arr.clear()
		return arr


class Solution:

	def customSort(self, arr, n):
		l1 = sorted(arr[0:n // 2])
		l2 = sorted(arr[n // 2:n])
		l1.extend(l2[::-1])
		for i in range(n):
			arr[i] = l1[i]
		return l1


class Solution:

	def customSort(self, arr, n):
		mid = n // 2
		a1 = arr[:mid]
		a2 = arr[mid:]
		a1.sort()
		a2.sort(reverse=True)
		c = a1 + a2
		for i in range(n):
			arr[i] = c[i]
		return arr


class Solution:

	def customSort(self, arr, n):
		f = []
		l = []
		for i in range(0, n // 2):
			f.append(arr[i])
		for i in range(n // 2, n):
			l.append(arr[i])
		f.sort()
		l.sort(reverse=True)
		arr.clear()
		for i in f:
			arr.append(i)
		for i in l:
			arr.append(i)


class Solution:

	def customSort(self, arr, n):
		l = arr[0:len(arr) // 2]
		l1 = arr[n // 2:n]
		l.sort()
		l1.sort(reverse=True)
		l.extend(l1)
		arr.clear()
		print(*l, end='')


class Solution:

	def customSort(self, arr, n):
		first = []
		second = []
		index = n // 2
		first = arr[:index]
		first.sort()
		second = arr[index:]
		second.sort()
		second.reverse()
		final = first + second
		for i in range(len(arr)):
			arr[i] = final[i]
		return arr