Given an array arr of size N and two integers l and r, the task is to sort the given array in non - decreasing order in the index range from l to r.
Example 1: 
Input:
N = 4
arr[] = {1, 5, 3, 2}
l = 2, r = 3
Output: {1, 5, 2, 3}
Explanation: After sorting array
will look like {1, 5, 2, 3} 
Ã¢â¬â¹Example 2: 
Input: 
N = 3
arr[] = {2, 3, 4}
l = 0, r = 2
Output: {2, 3, 4}
Explanation: Array is already sorted
Your Task:  
You don't need to read input or print anything. Your task is to complete the function partSort() which takes the array arr[], N, l and r as inputs and sorts the given the array in given range.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(1)
Constraints :
1 ≤ N ≤ 10^5
0 ≤ l, r ≤ N-1

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3
class Solution:
	def partSort(self, arr, n, l, r):
		# code here

Solutions:
class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			(l, r) = (r, l)
		temp = sorted(arr[l:r + 1])
		c = 0
		for i in range(l, r + 1):
			arr[i] = temp[c]
			c += 1


class Solution:

	def partSort(self, arr, n, l, r):
		if l < r:
			x = []
			for i in range(l, r + 1, 1):
				x.append(arr[i])
			x.sort()
			for i in range(0, len(x), 1):
				arr[l] = x[i]
				l += 1
		else:
			x = []
			for i in range(r, l + 1, 1):
				x.append(arr[i])
			x.sort()
			for i in range(0, len(x), 1):
				arr[r] = x[i]
				r += 1


class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			d = l
			l = r
			r = d
		a = arr[:l]
		b = arr[l:r + 1]
		c = arr[r + 1:]
		b.sort()
		a = a + b + c
		arr[:] = a[:]


class Solution:

	def partSort(self, arr, n, l, r):
		if l < r:
			arr[l:r + 1] = sorted(arr[l:r + 1])
		else:
			arr[r:l + 1] = sorted(arr[r:l + 1])


class Solution:

	def partSort(self, arr, n, l, r):
		if r > l:
			(l, r) = (l, r)
		else:
			(r, l) = (l, r)
		l1 = []
		l1.extend(arr[l:r + 1])
		l1.sort()
		j = 0
		for i in range(l, r + 1):
			arr.pop(i)
			arr.insert(i, l1[j])
			j += 1
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		sml = 0
		lrg = 0
		if l > r:
			(l, r) = (r, l)
		b = sorted(arr[l:r + 1])
		count = 0
		for i in range(l, r + 1):
			arr[i] = b[count]
			count += 1


class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			t = l
			l = r
			r = t
		a = arr[l:r + 1]
		mx = 0
		for i in a:
			if i > mx:
				mx = i
		if max(arr) < 110:
			tab = [0 for i in range(0, mx + 1)]
			for i in a:
				tab[i] += 1
			new = []
			for i in range(len(tab)):
				if tab[i] > 0:
					while tab[i] > 0:
						new.append(i)
						tab[i] -= 1
			j = 0
			for i in range(l, r + 1):
				arr[i] = new[j]
				j += 1
		else:
			a.sort()
			j = 0
			for i in range(l, r + 1):
				arr[i] = a[j]
				j += 1


class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			t = l
			l = r
			r = t
		a = arr[l:r + 1]
		a.sort()
		j = 0
		for i in range(l, r + 1):
			arr[i] = a[j]
			j += 1


class Solution:

	def partSort(self, arr, n, l, r):
		li = []
		j = 0
		if l < r:
			for i in range(l, r + 1):
				li.append(arr[i])
			li.sort()
			for i in range(l, r + 1):
				arr[i] = li[j]
				j += 1
		else:
			for i in range(r, l + 1):
				li.append(arr[i])
			li.sort()
			for i in range(r, l + 1):
				arr[i] = li[j]
				j += 1
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		i = min(l, r)
		j = max(l, r)
		arr2 = arr[:i] + sorted(arr[i:j + 1]) + arr[j + 1:]
		arr += arr2
		del arr[:n]


class Solution:

	def partSort(self, arr, n, l, r):
		if l < r:
			k = arr[l:r + 1]
			k = sorted(k)
			i = l
		else:
			k = arr[r:l + 1]
			i = r
			k = sorted(k)
		j = 0
		while j < len(k):
			arr[i] = k[j]
			i += 1
			j += 1
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		mi = min(l, r)
		ma = max(l, r)
		a = arr[mi:ma + 1]
		a.sort()
		j = 0
		for i in range(mi, ma + 1):
			arr[i] = a[j]
			j += 1
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		if l < r:
			l1 = arr[:l]
			l2 = arr[l:r + 1]
			l2.sort()
			l3 = arr[r + 1:]
			k = l1 + l2 + l3
		else:
			l1 = arr[:r]
			l2 = arr[r:l + 1]
			l2.sort()
			l3 = arr[l + 1:]
			k = l1 + l2 + l3
		for i in range(n):
			arr[i] = k[i]
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		mi = min(l, r)
		ma = max(l, r)
		ans = arr[mi:ma + 1]
		ans.sort()
		arr[mi:ma + 1] = ans


class Solution:

	def partSort(self, arr, n, l, r):
		x = []
		if l < r:
			x = arr[l:r + 1]
			x.sort()
			arr[l:r + 1] = x
		else:
			x = arr[r:l + 1]
			x.sort()
			arr[r:l + 1] = x


class Solution:

	def partSort(self, arr, n, l, r):
		l1 = min(l, r)
		r1 = max(l, r)
		ji = arr[l1:r1 + 1]
		ji.sort()
		arr[l1:r1 + 1] = ji


class Solution:

	def partSort(self, arr, n, l, r):
		xrr = []
		if abs(l - r) == n - 1:
			arr.sort()
			return arr
		mi = min(l, r)
		ma = max(l, r)
		for i in range(mi, ma + 1):
			xrr.append(arr[i])
		xrr.sort()
		x = 0
		for i in range(mi, ma + 1):
			arr[i] = xrr[x]
			x += 1
		return arr
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		arr = [int(x) for x in input().split()]
		(l, r) = input().split()
		(l, r) = (int(l), int(r))
		ob = Solution()
		ob.partSort(arr, n, l, r)
		for value in arr:
			print(value, end=' ')
		print()


class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			temp = l
			l = r
			r = temp
		lst = arr[l:r + 1]
		lst.sort()
		for itr in range(l, r + 1):
			arr[itr] = lst[itr - l]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		arr = [int(x) for x in input().split()]
		(l, r) = input().split()
		(l, r) = (int(l), int(r))
		ob = Solution()
		ob.partSort(arr, n, l, r)
		for value in arr:
			print(value, end=' ')
		print()


class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			(l, r) = (r, l)
		b = arr[l:r + 1]
		b.sort()
		k = 0
		for i in range(l, r + 1):
			arr[i] = b[k]
			k += 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		arr = [int(x) for x in input().split()]
		(l, r) = input().split()
		(l, r) = (int(l), int(r))
		ob = Solution()
		ob.partSort(arr, n, l, r)
		for value in arr:
			print(value, end=' ')
		print()


class Solution:

	def partSort(self, arr, n, l, r):
		if l < r:
			temp = arr[l:r + 1]
			temp.sort()
			arr[l:r + 1] = temp
		elif l > r:
			temp = arr[r:l + 1]
			temp.sort()
			arr[r:l + 1] = temp


class Solution:

	def partSort(self, arr, n, l, r):
		if r < l:
			(l, r) = (r, l)
		a = arr[:l]
		b = arr[l:r + 1]
		c = arr[r + 1:n]
		b.sort()
		a.extend(b)
		a.extend(c)
		arr[:n] = a[:n]
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		atbs = []
		for i in range(min(l, r), max(l, r) + 1):
			atbs.append(arr[i])
		atbs.sort()
		j = 0
		for i in range(min(l, r), max(r, l) + 1):
			arr[i] = atbs[j]
			j += 1
		return arr


class Solution:

	def partSort(self, arr, n, l, r):
		if l > r:
			t = arr[r:l + 1]
		else:
			t = arr[l:r + 1]
		t.sort()
		j = 0
		for i in range(n):
			if i >= l and i <= r:
				arr[i] = t[j]
				j += 1
			elif i >= r and i <= l:
				arr[i] = t[j]
				j += 1
		return arr