Given a singly linked list, sort the list (in ascending order) using insertion sort algorithm.
Example 1:
Input:
N = 10
Linked List = 30->23->28->30->11->14->
              19->16->21->25 
Output : 11 14 16 19 21 23 25 28 30 30 
Explanation :
The resultant linked list is sorted.
Example 2:
Input : 
N = 7
Linked List=19->20->16->24->12->29->30 
Output : 12 16 19 20 24 29 30 
Explanation : 
The resultant linked list is sorted.
Your task:
You don't need to read input or print anything. Your task is to complete the function insertionSort() which takes the head of the linked list, sorts the list using insertion sort algorithm and returns the head of the sorted linked list.
 
Expected Time Complexity : O(n^{2})
Expected Auxiliary Space : O(1)
 
Constraints:
1<=n<=10^3

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



'''

# Node Class

class Node:

    def __init__(self, data):   # data -> value stored in node

        self.data = data

        self.next = None

'''



class Solution:

    def insertionSort(self, head):

        #code here

Solutions:
class Solution:

	def insertionSort(self, ll):
		new = []
		head = ll
		while head:
			new.append(head.data)
			head = head.next
		new.sort()
		head = ll
		for i in new:
			head.data = i
			head = head.next
		return ll


class Solution:

	def insertionSort(self, head):
		root = Node(0)
		root.next = head
		(p, c) = (head, head.next)
		while c:
			if c.data > p.data:
				(p, c) = (c, c.next)
				continue
			temp = root
			while c.data > temp.next.data:
				temp = temp.next
			p.next = c.next
			c.next = temp.next
			temp.next = c
			c = p.next
		return root.next


class Solution:

	def insertionSort(self, head):
		tmp = None
		curr = head
		while curr:
			nxt = curr.next
			if tmp is None or tmp.data > curr.data:
				curr.next = tmp
				tmp = curr
			else:
				cur = tmp
				while cur.next and cur.next.data < curr.data:
					cur = cur.next
				(curr.next, cur.next) = (cur.next, curr)
			curr = nxt
		return tmp


class Solution:

	def insertionSort(self, head):
		sorted_list = None
		curr = head
		while curr:
			nxt = curr.next
			if sorted_list is None or sorted_list.data >= curr.data:
				curr.next = sorted_list
				sorted_list = curr
			else:
				temp = sorted_list
				while temp.next and temp.next.data < curr.data:
					temp = temp.next
				curr.next = temp.next
				temp.next = curr
			curr = nxt
		return sorted_list


class Solution:

	def insertionSort(self, head):
		m = []
		s = head
		while s:
			m.append(s.data)
			s = s.next
		s = head
		m.sort()
		while s:
			s.data = m.pop(0)
			s = s.next
		return head


class Solution:

	def insert(self, head, p):
		if not head or head.data >= p.data:
			p.next = head
			head = p
		else:
			q = head
			prev = None
			while q and q.data < p.data:
				prev = q
				q = q.next
			p.next = q
			prev.next = p
		return head

	def insertionSort(self, head):
		ans = None
		while head:
			next = head.next
			ans = self.insert(ans, head)
			head = next
		return ans


class Solution:

	def insertionSort(self, head):
		a = []
		while head != None:
			a.append(head.data)
			head = head.next
		a.sort()
		for i in a:
			print(i, end=' ')


class Solution:

	def insertionSort(self, head):
		dummy = Node(0)
		dummy.next = head
		(prev, cur) = (head, head.next)
		while cur:
			if cur.data > prev.data:
				(prev, cur) = (cur, cur.next)
				continue
			temp = dummy
			while cur.data > temp.next.data:
				temp = temp.next
			prev.next = cur.next
			cur.next = temp.next
			temp.next = cur
			cur = prev.next
		return dummy.next


class Solution:

	def insertionSort(self, head):
		l = []
		temp = head
		while temp != None:
			l.append(temp.data)
			temp = temp.next
		l = sorted(l)
		head = Node(l[0])
		t = head
		for j in range(1, len(l)):
			x = Node(l[j])
			head.next = x
			head = head.next
		return t


class Solution:

	def insertionSort(self, head):
		p = []
		a = head
		while a is not None:
			p.append(a.data)
			a = a.next
		head1 = None
		b = None
		for i in sorted(p):
			m = Node(i)
			if head1 is None:
				head1 = m
				b = head1
			else:
				b.next = m
				b = b.next
		return head1


class Solution:

	def insertionSort(self, head):
		nhead = head
		temp = head.next
		nhead.next = None
		while temp != None:
			node = temp
			temp = temp.next
			node.next = None
			itr = nhead
			prev = None
			while itr != None and node.data > itr.data:
				prev = itr
				itr = itr.next
			if itr != None:
				if prev == None:
					nhead = node
					node.next = itr
				else:
					prev.next = node
					node.next = itr
			else:
				prev.next = node
		return nhead


class Solution:

	def insertionSort(self, head):
		ptr = head
		lst = []
		while ptr:
			lst.append(ptr.data)
			ptr = ptr.next
		lst.sort()
		ptr = head
		i = 0
		while ptr:
			ptr.data = lst[i]
			i += 1
			ptr = ptr.next
		return head


def merge(head1, head2):
	if head2 == None:
		return head1
	tmp = temp = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not tmp:
				temp = head1
				tmp = head1
			else:
				tmp.next = head1
				tmp = tmp.next
			head1 = head1.next
		else:
			if not tmp:
				temp = head2
				tmp = head2
			else:
				tmp.next = head2
				tmp = tmp.next
			head2 = head2.next
	while head1:
		tmp.next = head1
		tmp = tmp.next
		head1 = head1.next
	while head2:
		tmp.next = head2
		tmp = tmp.next
		head2 = head2.next
	return temp

def mergesort(head):
	if head:
		if not head.next:
			return head
		slow = fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
		nxt = slow.next
		slow.next = None
		l = mergesort(head)
		r = mergesort(nxt)
		head = merge(l, r)
		return head
	return None

class Solution:

	def insertionSort(self, head):
		return mergesort(head)


class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Solution:

	def insertionSort(self, head):
		a = []
		n = head
		while n is not None:
			a += [n.data]
			n = n.next
		a = sorted(a)
		head = None
		head = Node(a[0])
		n = head
		for i in range(1, len(a)):
			no = Node(a[i])
			no.next = None
			n.next = no
			n = n.next
		return head


class Solution:

	def insertionSort(self, head):
		if head.next == None:
			return head
		temp = head
		while temp:
			temp2 = head
			while temp2.next != None:
				if temp2.data > temp2.next.data:
					(temp2.data, temp2.next.data) = (temp2.next.data, temp2.data)
				temp2 = temp2.next
			temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		l1 = []
		while head:
			l1.append(head.data)
			head = head.next
		l1.sort()
		for i in l1:
			print(i, end=' ')


class Solution:

	def insertionSort(self, head):
		curr_node = head.next
		while curr_node:
			prev_node = head
			while prev_node != curr_node:
				if prev_node.data > curr_node.data:
					(prev_node.data, curr_node.data) = (curr_node.data, prev_node.data)
				prev_node = prev_node.next
			curr_node = curr_node.next
		return head


class Solution:

	def insertionSort(self, head):
		start = Node(0)
		start.next = head
		root = start
		while root.next:
			next_node = root
			head = root
			while head.next:
				if head.next.data < next_node.next.data:
					next_node = head
				head = head.next
			temp = next_node.next
			next_node.next = next_node.next.next
			temp.next = root.next
			root.next = temp
			root = root.next
		return start.next


class Solution:

	def insertionSort(self, head):
		z = []
		while head is not None:
			z.append(head.data)
			head = head.next
		z.sort()
		z.append('x')
		head = None
		tail = None
		for ele in z:
			if ele != 'x':
				if head is None:
					newnode = Node(ele)
					head = newnode
					tail = newnode
				else:
					newnode = Node(ele)
					tail.next = newnode
					tail = newnode
		return head


class Solution:

	def insertionSort(self, head):
		P = head
		cur = head.next
		while cur:
			prev = None
			new = head
			while new and new.data < cur.data:
				prev = new
				new = new.next
			if new == cur:
				P = cur
				cur = cur.next
			elif prev:
				temp2 = cur.next
				prev.next = cur
				cur.next = new
				P.next = temp2
				cur = temp2
			else:
				temp2 = cur.next
				head = cur
				cur.next = new
				P.next = temp2
				cur = temp2
		return head


class Solution:

	def insertionSort(self, head):
		b = []
		tmp = head
		while tmp:
			b.append(tmp.data)
			tmp = tmp.next
		tmp = head
		b.sort()
		for i in b:
			tmp.data = i
			tmp = tmp.next
		return head


class Solution:

	def insertionSort(self, head):
		tek = head
		while tek.next != None:
			tek1 = tek.next
			while tek1 != None:
				if tek1.data < tek.data:
					temp = tek.data
					tek.data = tek1.data
					tek1.data = temp
				tek1 = tek1.next
			tek = tek.next
		return head


class Solution:

	def insertionSort(self, head):
		dummy = Node(-1)
		cur = head
		while cur:
			temp = dummy
			while temp.next and cur.data > temp.next.data:
				temp = temp.next
			t = temp.next
			temp.next = cur
			nxt = cur.next
			cur.next = t
			cur = nxt
		return dummy.next


class Solution:

	def insertionSort(self, head):
		t = []
		temp = head
		while temp:
			t.append(temp.data)
			temp = temp.next
		t = sorted(t)
		temp = head
		for i in t:
			temp.data = i
			temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		if not head or not head.next:
			return head
		sorted_head = Node(0)
		sorted_head.next = head
		curr = head.next
		tail = head
		while curr:
			if curr.data >= tail.data:
				tail = curr
				curr = curr.next
			else:
				prev = sorted_head
				while prev.next.data < curr.data:
					prev = prev.next
				tail.next = curr.next
				curr.next = prev.next
				prev.next = curr
				curr = tail.next
		return sorted_head.next


class Solution:

	def insertionSort(self, head):
		new_node = Node(0)
		x = []
		curr1 = head
		tmp_node = new_node
		while curr1:
			x.append(curr1.data)
			curr1 = curr1.next
		for node in sorted(x):
			tmp_node.next = Node(node)
			tmp_node = tmp_node.next
		return new_node.next


class Solution:

	def insertionSort(self, head):
		a = []
		h = head
		while head:
			a.append(head.data)
			head = head.next
		a.sort()
		head = h
		for i in a:
			h.data = i
			h = h.next
		return head


class Solution:

	def insertionSort(self, head):
		arr = []
		dup = head
		while dup:
			arr.append(dup.data)
			dup = dup.next
		arr.sort()
		a = head
		for i in arr:
			a.data = i
			a = a.next
		return head


class Solution:

	def insertionSort(self, head):
		dummy = Node(0)
		curr = head
		while curr:
			prev = dummy
			while prev.next and prev.next.data < curr.data:
				prev = prev.next
			nxt = curr.next
			curr.next = prev.next
			prev.next = curr
			curr = nxt
		return dummy.next


class Solution:

	def insertionSort(self, head):
		arr = []
		curr = head
		while curr:
			arr.append(curr.data)
			curr = curr.next
		n = len(arr)
		for i in range(1, n):
			key = arr[i]
			j = i - 1
			while j >= 0 and key < arr[j]:
				arr[j + 1] = arr[j]
				j -= 1
			arr[j + 1] = key
		new = Node(-1)
		tail = new
		k = 0
		while k != n:
			tail.next = Node(arr[k])
			tail = tail.next
			k += 1
		return new.next


class Solution:

	def insertionSort(self, head):
		l = []
		while head:
			l.append(head.data)
			head = head.next
		l.sort()
		s = ''
		for x in l:
			s += str(x) + ' '
		return Node(s)


class Solution:

	def insertionSort(self, head):
		b = []
		tmp = head
		while tmp != None:
			b.append(tmp.data)
			tmp = tmp.next
		n = len(b)
		for i in range(1, n):
			y = b[i]
			j = i - 1
			while j >= 0 and y < b[j]:
				b[j + 1] = b[j]
				j -= 1
			b[j + 1] = y
		tmp = head
		for i in b:
			tmp.data = i
			tmp = tmp.next
		return head


class Solution:

	def insertionSort(self, head):
		arr = []
		while head != None:
			arr.append(head.data)
			head = head.next
		arr.sort()
		return Node(' '.join(map(str, arr)))


class Solution:

	def insertionSort(self, head):
		l = []
		temp = head
		while head:
			l.append(head.data)
			head = head.next
		l.sort()
		head = temp
		for i in l:
			head.data = i
			head = head.next
		return temp


class Solution:

	def insertionSort(self, head):
		k = []
		while head:
			k.append(head.data)
			head = head.next
		k.sort()
		nl = Node(0)
		op = nl
		for i in k:
			op.next = Node(i)
			op = op.next
		return nl.next


class Solution:

	def insertionSort(self, head):
		if head == None or head.next == None:
			return head
		pre = head
		slow = head
		fast = head
		while fast and fast.next:
			pre = slow
			slow = slow.next
			fast = fast.next.next
		mid = slow
		pre.next = None
		h1 = self.insertionSort(head)
		h2 = self.insertionSort(mid)
		mergeed = self.merge(h1, h2)
		return mergeed

	def merge(self, h1, h2):
		dummy = Node(0)
		temp = dummy
		while h1 and h2:
			if h1.data <= h2.data:
				temp.next = h1
				h1 = h1.next
				temp = temp.next
			else:
				temp.next = h2
				h2 = h2.next
				temp = temp.next
		if h1:
			temp.next = h1
		if h2:
			temp.next = h2
		return dummy.next


class Solution:

	def insertionSort(self, head):
		if head is None or head.next is None:
			return head
		dummy = Node(0)
		dummy.next = head
		curr = head
		while curr.next:
			if curr.next.data < curr.data:
				pre = dummy
				while pre.next.data < curr.next.data:
					pre = pre.next
				temp = curr.next
				curr.next = temp.next
				temp.next = pre.next
				pre.next = temp
			else:
				curr = curr.next
		return dummy.next


class Solution:

	def insertionSort(self, head):
		a = []
		b = head
		while b:
			a.append(b.data)
			b = b.next
		a.sort()
		l = k = Node(a[0])
		for i in range(1, len(a)):
			l.next = Node(a[i])
			l = l.next
		return k


class Solution:

	def insertionSort(self, head):
		a = []
		b = head
		while b:
			a.append(b.data)
			b = b.next
		a.sort()
		f = g = Node(a[0])
		for i in range(1, len(a)):
			f.next = Node(a[i])
			f = f.next
		return g


class Solution:

	def insertionSort(self, head):
		li = []
		ans = Node(0)
		counter = ans
		while head != None:
			li.append(head.data)
			head = head.next
		li.sort()
		for i in range(len(li)):
			counter.next = Node(li[i])
			counter = counter.next
		return ans.next


class Solution:

	def insertionSort(self, head):
		res = []
		temp = head
		while temp != None:
			res.append(temp.data)
			temp = temp.next
		res.sort()
		head = Node(res[0])
		temp = head
		for i in range(1, len(res)):
			temp.next = Node(res[i])
			temp = temp.next
		return head


class Solution:

	def length(self, head):
		if head is None:
			return 0
		ct = 0
		temp = head
		while temp:
			ct += 1
			temp = temp.next
		return ct

	def insertionSort(self, head):
		n = self.length(head)
		for i in range(n - 1):
			temp = head
			for j in range(n - i - 1):
				if temp.data > temp.next.data:
					(temp.data, temp.next.data) = (temp.next.data, temp.data)
				temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		ptr = head
		t = None
		while ptr:
			t = ptr.next
			while t:
				if t.data < ptr.data:
					temp = t.data
					t.data = ptr.data
					ptr.data = temp
				t = t.next
			ptr = ptr.next
		return head


class Solution:

	def insertionSort(self, head):
		cur = head
		x = []
		while cur:
			x.append(cur.data)
			cur = cur.next
		x.sort()
		temp = head
		i = 0
		while temp:
			temp.data = x[i]
			i += 1
			temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		if head is None or head.next is None:
			return head
		l = []
		while head is not None:
			l.append(head.data)
			head = head.next
		l.sort()
		head = Node(l[0])
		temp = head
		for i in range(1, len(l)):
			temp.next = Node(l[i])
			temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		temp1 = head
		temp2 = head
		l = []
		while temp1:
			l.append(temp1.data)
			temp1 = temp1.next
		l.sort()
		for item in l:
			temp2.data = item
			temp2 = temp2.next
		return head


class Solution:

	def insertionSort(self, head):
		temp = head
		l = []
		while temp:
			l.append(temp.data)
			temp = temp.next
		l = sorted(l)
		head = None
		for i in l:
			node = Node(i)
			if head is None:
				head = node
				cur = node
			else:
				cur.next = node
			cur = node
		return head


class Solution:

	def insertionSort(self, head):
		if head == None:
			return
		currNode = head
		while currNode != None:
			prev = head
			temp = head.next
			while temp != None:
				if temp.data < prev.data:
					(temp.data, prev.data) = (prev.data, temp.data)
				temp = temp.next
				prev = prev.next
			currNode = currNode.next
		return head


class Solution:

	def insertionSort(self, head):
		data = []
		ptr = head
		while ptr != None:
			data.append(ptr.data)
			ptr = ptr.next
		data = sorted(data)
		ptr = head
		i = 0
		while ptr != None:
			ptr.data = data[i]
			ptr = ptr.next
			i = i + 1
		return head


class Solution:

	def insertionSort(self, head):
		list1 = []
		t1 = head
		while t1:
			list1.append(t1.data)
			t1 = t1.next
		list1.sort()
		temp = head
		i = 0
		while temp != None:
			temp.data = list1[i]
			i += 1
			temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		curr = head
		arr = []
		brr = []
		while curr:
			arr.append(curr.data)
			brr.append(curr)
			curr = curr.next
		l = 0
		r = 1
		while r < len(arr):
			a = r
			while l < r:
				if arr[r] < arr[r - 1]:
					temp = arr[r]
					arr[r] = arr[r - 1]
					arr[r - 1] = temp
					temp1 = brr[r]
					brr[r] = brr[r - 1]
					brr[r - 1] = temp1
					r -= 1
				else:
					break
			r = a + 1
		for i in range(len(brr)):
			if i == len(brr) - 1:
				brr[i].next = None
				break
			brr[i].next = brr[i + 1]
		return brr[0]


class Solution:

	def insertionSort(self, head):
		li = []
		while head:
			li.append(head.data)
			head = head.next
		li.sort()
		for x in li:
			newNode = Node(x)
			if head == None:
				head = newNode
				temp = head
			else:
				temp.next = newNode
				temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):

		def print_list():
			node = head
			while node != None:
				print(node.data, end=' ')
				node = node.next
			print()
		if head.next == None or head.data == None:
			return head
		else:
			node = head.next
			while node != None:
				curr_val = node.data
				comp_node = head
				while comp_node != node and comp_node.data <= curr_val:
					comp_node = comp_node.next
				node_list = [comp_node]
				while comp_node != node:
					comp_node = comp_node.next
					node_list.append(comp_node)
				for i in range(len(node_list) - 1, 0, -1):
					(node_list[i].data, node_list[i - 1].data) = (node_list[i - 1].data, node_list[i].data)
				node = node.next
			return head


class Solution:

	def insertionSort(self, head):
		curr = head
		Index = None
		if head is None:
			return head
		else:
			while curr != None:
				Index = curr.next
				while Index != None:
					if curr.data > Index.data:
						temp = curr.data
						curr.data = Index.data
						Index.data = temp
					Index = Index.next
				curr = curr.next
		return head


class Solution:

	def insertionSort(self, head):
		n = 0
		a = head
		while a:
			n += 1
			a = a.next
		arr = [int] * n
		a = head
		i = 0
		while a:
			arr[i] = a.data
			a = a.next
			i += 1
		arr.sort()
		i = 0
		a = Node(arr[i])
		c = a
		i += 1
		while i < n:
			a.next = Node(arr[i])
			i += 1
			a = a.next
		return c


class Solution:

	def insertionSort(self, head):
		temp = head.next
		while temp:
			temp1 = head
			while temp1 != temp:
				if temp.data < temp1.data:
					(temp.data, temp1.data) = (temp1.data, temp.data)
				temp1 = temp1.next
			temp = temp.next
		return head


class Solution:

	def insertionSort(self, head):
		ans = Node(0)

		def add(node):
			curr = ans
			prev = ans
			while curr:
				if curr.data < node.data:
					prev = curr
					curr = curr.next
				else:
					break
			node.next = prev.next
			prev.next = node
		while head:
			temp = head
			head = head.next
			add(temp)
		ans = ans.next
		return ans


class Solution:

	def insertionSort(self, head):
		temp = []
		while head:
			temp.append(head.data)
			head = head.next
		temp.sort()
		curr = dummy = Node(0)
		for i in temp:
			curr.next = Node(i)
			curr = curr.next
		return dummy.next


class Solution:

	def insertionSort(self, head):
		res = []
		while head:
			res.append(head.data)
			head = head.next
		res.sort()
		curr = dummy = Node(0)
		for e in res:
			curr.next = Node(e)
			curr = curr.next
		return dummy.next


class Solution:

	def insertionSort(self, head):
		x = []
		cur = head
		while cur:
			x.append(cur.data)
			cur = cur.next
		x.sort()
		cur = head
		for i in x:
			cur.data = i
			cur = cur.next
		return head


class Solution:

	def insertionSort(self, head):
		curr = head
		l = []
		while curr != None:
			l.append(curr.data)
			curr = curr.next
		l.sort()
		n = len(l)
		i = 0
		curr = head
		while curr != None and i < n:
			curr.data = l[i]
			curr = curr.next
			i += 1
		return head
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
INF = float('inf')

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

def printList(head):
	if head is None:
		print(' ')
		return
	curr_node = head
	while curr_node:
		print(curr_node.data, end=' ')
		curr_node = curr_node.next
	print(' ')
if __name__ == '__main__':
	t = int(input())
	for cases in range(t):
		n = int(input())
		a = Node(INF)
		nodes = list(map(int, input().strip().split()))
		ptr = a
		for x in nodes:
			ptr.next = Node(INF)
			ptr = ptr.next
			ptr.data = x
		a = a.next
		ob = Solution()
		head = ob.insertionSort(a)
		printList(head)


class Solution:

	def insertionSort(self, head):
		dummy = Node(0)
		dummy.next = head
		prev = head
		curr = head.next
		while curr:
			if curr.data > prev.data:
				prev = curr
				curr = curr.next
				continue
			temp = dummy
			while curr.data > temp.next.data:
				temp = temp.next
			prev.next = curr.next
			curr.next = temp.next
			temp.next = curr
			curr = prev.next
		return dummy.next
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
INF = float('inf')

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

def printList(head):
	if head is None:
		print(' ')
		return
	curr_node = head
	while curr_node:
		print(curr_node.data, end=' ')
		curr_node = curr_node.next
	print(' ')
if __name__ == '__main__':
	t = int(input())
	for cases in range(t):
		n = int(input())
		a = Node(INF)
		nodes = list(map(int, input().strip().split()))
		ptr = a
		for x in nodes:
			ptr.next = Node(INF)
			ptr = ptr.next
			ptr.data = x
		a = a.next
		ob = Solution()
		head = ob.insertionSort(a)
		printList(head)


class Solution:

	@classmethod
	def insert(cls, head: 'Node', data: int) -> 'Node':
		if not head:
			return Node(data)
		elif data <= head.data:
			temp = Node(data)
			temp.next = head
			return temp
		else:
			head.next = cls.insert(head.next, data)
			return head

	@classmethod
	def insertionSort(cls, head: 'Node'):
		temp = head
		head = None
		while temp:
			head = cls.insert(head, temp.data)
			temp = temp.next
		return head
import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
INF = float('inf')

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

def printList(head):
	if head is None:
		print(' ')
		return
	curr_node = head
	while curr_node:
		print(curr_node.data, end=' ')
		curr_node = curr_node.next
	print(' ')
if __name__ == '__main__':
	t = int(input())
	for cases in range(t):
		n = int(input())
		a = Node(INF)
		nodes = list(map(int, input().strip().split()))
		ptr = a
		for x in nodes:
			ptr.next = Node(INF)
			ptr = ptr.next
			ptr.data = x
		a = a.next
		ob = Solution()
		head = ob.insertionSort(a)
		printList(head)


class Solution:

	def insertionSort(self, head):
		dummy = Node(0)
		dummy.next = head
		(pre, cur) = (head, head.next)
		while cur:
			nex = cur.next
			if cur.data < pre.data:
				itr = dummy
				while itr.next.data < cur.data:
					itr = itr.next
				pre.next = pre.next.next
				cur.next = itr.next
				itr.next = cur
				cur = pre.next
			else:
				pre = cur
				cur = cur.next
		return dummy.next


class Solution:

	def insertionSort(self, head):
		lst = []
		itr = head
		while itr:
			lst.append(itr.data)
			itr = itr.next
		lst = sorted(lst, reverse=True)
		head = None
		for i in lst:
			node = Node(i)
			node.next = head
			head = node
		return head


class Solution:

	def insertionSort(self, head):
		x = []
		while head:
			x.append(head.data)
			head = head.next
		for i in sorted(x):
			print(i, end=' ')