Given an array of numbers of size N. It is also given that the array elements are in range from 0 to N^{2} – 1. Sort the given array in linear time.
Example 1:
Input:
N = 7
arr[] = {40, 12, 45, 32, 33, 1, 22}
Output: 1 12 22 32 33 40 45
Explanation: Output is the sorted version of the
given array.
Ã¢â¬â¹Example 2:
Input: 
N = 5
arr[] = {24, 12, 0, 15, 8}
Output: 0 8 12 15 24
Explanation: Output is the sorted version of the
given array.
Your Task:
You don't need to read input or print anything. Your task is to complete the function sort () which takes an array arr[] and its size N as inputs and sorts the array in non-decreasing order. 
Note: You have to modify the input array such that it becomes sorted in non-decreasing order.
Expected Time Complexity: O(N). 
Expected Auxiliary Space: O(N).
Constraints:
1 <= N <= 10^4

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Square root algorithms

Starter code: #User function Template for python3

class Solution:

    def sort(self, arr, n):
        
        # code here

Solutions:
class Solution:

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


class Solution:

	def countSort(self, arr, n, e):
		ans = [0] * n
		count = [0] * n
		for a in arr:
			count[a // e % n] += 1
		for i in range(1, n):
			count[i] += count[i - 1]
		for i in range(n - 1, -1, -1):
			ans[count[arr[i] // e % n] - 1] = arr[i]
			count[arr[i] // e % n] -= 1
		for i in range(n):
			arr[i] = ans[i]

	def sort(self, arr, n):
		self.countSort(arr, n, 1)
		self.countSort(arr, n, n)


class Solution:

	def sort(self, arr, n):
		c = arr.sort()
		return c


class Solution:

	def sort(self, arr, n):
		s = arr.sort()
		return s


class Solution:

	def radix(self, arr, n, p):
		ans = [0] * n
		cnt = [0] * n
		for i in range(n):
			dx = arr[i] // n ** p % n
			cnt[dx] += 1
		for i in range(1, n):
			cnt[i] += cnt[i - 1]
		for i in range(n - 1, -1, -1):
			dx = arr[i] // n ** p % n
			ans[cnt[dx] - 1] = arr[i]
			cnt[dx] -= 1
		for i in range(n):
			arr[i] = ans[i]

	def sort(self, arr, n):
		index = len(str(max(arr)))
		for p in range(2):
			self.radix(arr, n, p)


class Solution:

	def sort(self, arr, n):
		maxm = max(arr)
		exp = 1
		while maxm // exp > 0:
			output = [0] * n
			count = [0] * 10
			for i in range(n):
				idx = arr[i] // exp
				count[idx % 10] += 1
			for i in range(1, 10):
				count[i] += count[i - 1]
			for i in range(n - 1, -1, -1):
				idx = arr[i] // exp
				output[count[idx % 10] - 1] = arr[i]
				count[idx % 10] -= 1
			for i in range(n):
				arr[i] = output[i]
			exp *= 10
		return arr


class Solution:

	def sort(self, T, n):
		counts = [0 for _ in range(n)]
		output = [0 for _ in range(n)]
		for i in range(n):
			counts[T[i] % n] += 1
		for i in range(1, n):
			counts[i] += counts[i - 1]
		for i in range(n - 1, -1, -1):
			counts[T[i] % n] -= 1
			output[counts[T[i] % n]] = T[i]
		for i in range(n):
			T[i] = output[i]
		counts = [0 for _ in range(n)]
		output = [0 for _ in range(n)]
		for i in range(n):
			counts[T[i] // n] += 1
		for i in range(1, n):
			counts[i] += counts[i - 1]
		for i in range(n - 1, -1, -1):
			counts[T[i] // n] -= 1
			output[counts[T[i] // n]] = T[i]
		for i in range(n):
			T[i] = output[i]


class Solution:

	def sort(self, arr, n):
		arr1 = arr[:]
		ma = max(arr1)
		k = 0
		while ma != 0:
			k += 1
			ma = ma // 10
		li = [[] for i in range(10)]
		k1 = 1
		while k1 <= k:
			for i in arr1:
				li[i % pow(10, k1) // max(1, pow(10, k1 - 1))].append(i)
			arr1 = []
			for i in li:
				arr1.extend(i)
			li = [[] for i in range(10)]
			k1 += 1
		for i in range(n):
			arr[i] = arr1[i]


class Solution:

	def sort(self, arr, n):
		aux = [0] * n
		count = [0] * n
		for i in range(n):
			count[arr[i] % n] += 1
		for i in range(1, n):
			count[i] += count[i - 1]
		for i in range(n - 1, -1, -1):
			aux[count[arr[i] % n] - 1] = arr[i]
			count[arr[i] % n] -= 1
		for i in range(n):
			arr[i] = aux[i]
			count[i] = 0
		for i in range(n):
			count[arr[i] // n % n] += 1
		for i in range(1, n):
			count[i] += count[i - 1]
		for i in range(n - 1, -1, -1):
			aux[count[arr[i] // n % n] - 1] = arr[i]
			count[arr[i] // n % n] -= 1
		for i in range(n):
			arr[i] = aux[i]


class Solution:

	def radixsort(self, arr, n, exp):
		output = [0] * n
		count = [0] * n
		for i in range(n):
			count[arr[i] // exp % n] += 1
		for i in range(1, n):
			count[i] += count[i - 1]
		for i in range(n - 1, -1, -1):
			output[count[arr[i] // exp % n] - 1] = arr[i]
			count[arr[i] // exp % n] -= 1
		for i in range(n):
			arr[i] = output[i]

	def sort(self, arr, n):
		self.radixsort(arr, n, 1)
		self.radixsort(arr, n, n)
		return arr


class Solution:

	def sort(self, arr, n):

		def countSort(arr, exp):
			newArr = [[] for i in range(10)]
			for i in range(len(arr)):
				newArr[arr[i] // exp % 10].append(arr[i])
			j = 0
			for i in newArr:
				for k in i:
					arr[j] = k
					j += 1
			return arr
		maxLen = len(str(n ** 2))
		for i in range(maxLen):
			exp = 10 ** i
			countSort(arr, exp)
		return arr


class Solution:

	def sort(self, arr, n):
		B = n
		for j in range(2):
			freq = [0] * n
			for i in range(n):
				num_digit = arr[i] // B ** j % B
				freq[num_digit] += 1
			k = 1
			while k < B:
				freq[k] += freq[k - 1]
				k += 1
			arr_copy = arr.copy()
			for i in range(n - 1, -1, -1):
				num_digit = arr_copy[i] // B ** j % B
				arr[freq[num_digit] - 1] = arr_copy[i]
				freq[num_digit] -= 1
		return arr


class Solution:

	def counting(self, n, arr, div):
		count = [0] * n
		output = [0] * n
		for i in arr:
			count[i // div % n] += 1
		for j in range(1, n):
			count[j] += count[j - 1]
		for k in range(n - 1, -1, -1):
			output[count[arr[k] // div % n] - 1] = arr[k]
			count[arr[k] // div % n] -= 1
		for i in range(n):
			arr[i] = output[i]

	def sort(self, arr, n):
		self.counting(n, arr, 1)
		self.counting(n, arr, n)


class Solution:

	def sort(self, arr, n):
		return arr.sort()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = [int(x) for x in input().split()]
		solObj = Solution()
		solObj.sort(arr, N)
		for i in arr:
			print(i, end=' ')
		print()


class Solution:

	def sort(self, arr, n):
		if len(arr) > 1:
			m = len(arr) // 2
			l = arr[:m]
			r = arr[m:]
			self.sort(l, len(l))
			self.sort(r, len(r))
			i = j = k = 0
			while i < len(l) and j < len(r):
				if l[i] < r[j]:
					arr[k] = l[i]
					i = i + 1
				else:
					arr[k] = r[j]
					j = j + 1
				k = k + 1
			while i < len(l):
				arr[k] = l[i]
				i = i + 1
				k = k + 1
			while j < len(r):
				arr[k] = r[j]
				j = j + 1
				k = k + 1


import numpy as np

class Solution:

	def count_sort(self, arr, n, exp):
		idxs = np.zeros((n,), dtype=int)
		output_arr = np.zeros((n,), dtype=int)
		for i in range(len(arr)):
			idxs[int(arr[i] // exp % n)] += 1
		i = 1
		while i < n:
			idxs[i] += idxs[i - 1]
			i += 1
		i = n - 1
		while i >= 0:
			output_arr[idxs[int(arr[i] / exp % n)] - 1] = arr[i]
			idxs[int(arr[i] / exp % n)] -= 1
			i -= 1
		for i in range(n):
			arr[i] = output_arr[i]

	def sort(self, arr, n):
		self.count_sort(arr, n, 1)
		self.count_sort(arr, n, n)


from queue import PriorityQueue

class Solution:

	def sort(self, arr, n):
		q = PriorityQueue(n)
		for i in range(n):
			q.put(arr[i])
		i = 0
		while q.empty() == False:
			arr[i] = q.get()
			i += 1
		return arr


class Solution:

	def sort(self, arr, n):
		arr.sort()
		return
		f = [0 for i in range(n * n)]
		for i in range(n):
			f[arr[i]] += 1
		k = 0
		for i in range(n * n):
			if f[i] != 0:
				for j in range(f[i]):
					arr[k] = i
					k += 1
		return arr


class Solution:

	def countSort(self, arr, j):
		n = len(arr)
		B = [0] * n
		C = [0] * n
		for i in range(n):
			C[arr[i][j]] += 1
		for i in range(1, n):
			C[i] += C[i - 1]
		for i in range(n - 1, -1, -1):
			C[arr[i][j]] -= 1
			B[C[arr[i][j]]] = arr[i]
		for i in range(n):
			arr[i] = B[i]

	def preprocessing(self, arr):
		n = len(arr)
		for i in range(n):
			a = arr[i] // n
			b = arr[i] % n
			arr[i] = (a, b)
		return arr

	def sort(self, arr, n):
		arr = self.preprocessing(arr)
		self.countSort(arr, 1)
		self.countSort(arr, 0)
		for i in range(n):
			arr[i] = arr[i][0] * n + arr[i][1]
		return arr


class Solution:

	def sort(self, arr1, n):
		global arr
		arr = sorted(arr1)


class Solution:

	def sort(self, arr, n):
		if n <= 1:
			return arr
		bucket = [[] for _ in range(n // 2)]
		mx = n * n
		for i in range(n):
			bi = n // 2 * arr[i] // mx
			bucket[bi].append(arr[i])
		for i in range(n // 2):
			bucket[i].sort()
		index = 0
		for i in bucket:
			for j in i:
				arr[index] = j
				index += 1


class Solution:

	def sort(self, arr, n):
		for i in range(1, len(arr)):
			key = arr[i]
			j = i - 1
			while j >= 0 and key < arr[j]:
				arr[j + 1] = arr[j]
				j -= 1
			arr[j + 1] = key


class Solution:

	def sort(self, arr, n):
		base = n
		max_elem = n ** 2 - 1
		freq = [0] * base
		ans = [0] * n
		digits = 0
		count = 0
		while max_elem > 0:
			count += 1
			max_elem /= base
		exponent = 0
		while exponent < count:
			for i in range(0, n):
				freq[arr[i] // base ** exponent % base] += 1
			for i in range(1, base):
				freq[i] += freq[i - 1]
			for i in range(N - 1, -1, -1):
				ans[freq[arr[i] // base ** exponent % base] - 1] = arr[i]
				freq[arr[i] // base ** exponent % base] -= 1
			for i in range(0, n):
				arr[i] = ans[i]
			for i in range(0, base):
				freq[i] = 0
			exponent += 1
		return arr


class Solution:

	def RadixSort(self, arr, n, digit, count, Aux):
		for i in range(n):
			count[arr[i] // digit % n] += 1
		for i in range(1, n):
			count[i] += count[i - 1]
		for i in range(n - 1, -1, -1):
			Aux[count[arr[i] // digit % n] - 1] = arr[i]
			count[arr[i] // digit % n] -= 1
		for i in range(n):
			arr[i] = Aux[i]
			count[i] = 0
		return

	def sort(self, arr, n):
		count = [0] * n
		Aux = [0] * n
		self.RadixSort(arr, n, 1, count, Aux)
		self.RadixSort(arr, n, n, count, Aux)
		return


class Solution:

	def sort(self, arr, n):
		self.quicksort(arr, 0, n - 1)
		return arr

	def quicksort(self, arr, l, r):
		if l >= r:
			return
		p = self.partition(arr, l, r)
		self.quicksort(arr, l, p - 1)
		self.quicksort(arr, p + 1, r)

	def partition(self, arr, l, r):
		p = arr[r]
		j = l
		for i in range(l, r + 1):
			if arr[i] <= p:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		return j - 1


class Solution:

	def sort(self, arr, n):
		z = sorted(arr)
		arr.clear()
		arr += z


class Solution:

	def no_of_digit(self, n):
		s = n
		count = 0
		while s > 0:
			s = s // 10
			count += 1
		return count

	def nth_digit(self, no, n):
		num = no
		rem = 0
		for i in range(0, n):
			if num == 0:
				return 0
			rem = num % 10
			num = num // 10
		return rem

	def countingSort(self, a, n, d):
		ans = a.copy()
		f = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for i in range(n):
			f[self.nth_digit(ans[i], d)] += 1
		for i in range(1, 10):
			f[i] += f[i - 1]
		for i in range(n - 1, -1, -1):
			f[self.nth_digit(ans[i], d)] -= 1
			a[f[self.nth_digit(ans[i], d)]] = ans[i]

	def sort(self, a, n):
		no = self.no_of_digit(n ** 2 - 1)
		ans = a
		for i in range(1, no + 1):
			self.countingSort(ans, n, i)


class Solution:

	def sort(self, arr, n):
		for i in range(n):
			t = i
			for j in range(t, n):
				if arr[t] >= arr[j]:
					t = j
			(arr[i], arr[t]) = (arr[t], arr[i])
		return arr