Given a random set of numbers, Print them in sorted order.
Example 1:
Input:
N = 4
arr[] = {1, 5, 3, 2}
Output: {1, 2, 3, 5}
Explanation: After sorting array will 
be like {1, 2, 3, 5}.
Example 2:
Input:
N = 2
arr[] = {3, 1}
Output: {1, 3}
Explanation: After sorting array will
be like {1, 3}.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sortArr() which takes the list of integers and the size N as inputs and returns the modified list.
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Starter code: #User function Template for python3

class Solution:

    def sortArr(self, arr, n): 

        #code here

Solutions:
class Solution:

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


class Solution:

	def sortArr(self, arr, n):
		a = sorted(arr)
		return a


class Solution:

	def sortArr(self, arr, n):
		if n > 1:
			mid = n // 2
			left_arr = arr[:mid]
			right_arr = arr[mid:]
			self.sortArr(left_arr, len(left_arr))
			self.sortArr(right_arr, len(right_arr))
			p = q = r = 0
			while p < len(left_arr) and q < len(right_arr):
				if left_arr[p] < right_arr[q]:
					arr[r] = left_arr[p]
					p += 1
				else:
					arr[r] = right_arr[q]
					q += 1
				r += 1
			while p < len(left_arr):
				arr[r] = left_arr[p]
				p += 1
				r += 1
			while q < len(right_arr):
				arr[r] = right_arr[q]
				q += 1
				r += 1
			return arr


class Solution:

	def sortArr(self, arr, n):

		def mergesort(arr):
			if len(arr) > 1:
				mid = len(arr) // 2
				l = arr[mid:]
				r = arr[:mid]
				mergesort(l)
				mergesort(r)
				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
			return arr
		return mergesort(arr)


class Solution:

	def sortArr(self, arr, n):
		arr.sort()
		ans = []
		for i in range(n):
			ans.append(arr[i])
		return ans


class Solution:

	def sortArr(self, arr, n):
		if len(arr) <= 1:
			return arr
		else:
			(left, right) = self.split(arr)
			left_sort = self.sortArr(left, n)
			right_sort = self.sortArr(right, n)
			return self.merge(left_sort, right_sort)

	def split(self, arr):
		mid = len(arr) // 2
		left_half = arr[:mid]
		right_half = arr[mid:]
		return (left_half, right_half)

	def merge(self, left, right):
		i = 0
		j = 0
		sorted_arr = []
		while i < len(left) and j < len(right):
			if left[i] < right[j]:
				sorted_arr.append(left[i])
				i += 1
			else:
				sorted_arr.append(right[j])
				j += 1
		sorted_arr += left[i:]
		sorted_arr += right[j:]
		return sorted_arr


class Solution:

	def sortArr(self, arr, n):
		n = len(arr)
		if n <= 1:
			return arr
		mid = n // 2
		left_half = arr[:mid]
		right_half = arr[mid:]
		left_half = self.sortArr(left_half, n)
		right_half = self.sortArr(right_half, n)
		return self.merge(left_half, right_half)

	def merge(self, left, right):
		i = j = 0
		result = []
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
				result.append(left[i])
				i += 1
			else:
				result.append(right[j])
				j += 1
		while i < len(left):
			result.append(left[i])
			i += 1
		while j < len(right):
			result.append(right[j])
			j += 1
		return result


class Solution:

	def sortArr(self, arr, n):
		c = sorted(arr)
		return c


class Solution:

	def partition(self, a, start, end):
		j = start - 1
		pivot = a[end]
		for i in range(start, end):
			if arr[i] < pivot:
				j += 1
				(a[j], a[i]) = (a[i], a[j])
		j += 1
		(a[j], a[end]) = (a[end], a[j])
		return j

	def quicksort(self, arr, start, end):
		if start < end:
			pivot = self.partition(arr, start, end)
			self.quicksort(arr, start, pivot - 1)
			self.quicksort(arr, pivot + 1, end)

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


class Solution:

	def sortArr(self, arr, n):
		b = sorted(arr)
		return b


class Solution:

	def sortArr(self, arr, n):
		self.mergesort(arr, 0, n - 1)
		return arr

	def mergesort(self, arr, low, high):
		if low >= high:
			return
		mid = (low + high) // 2
		self.mergesort(arr, low, mid)
		self.mergesort(arr, mid + 1, high)
		self.merge(arr, low, mid, high)

	def merge(self, arr, low, mid, high):
		temp = []
		left = low
		right = mid + 1
		while left <= mid and right <= high:
			if arr[left] <= arr[right]:
				temp.append(arr[left])
				left = left + 1
			else:
				temp.append(arr[right])
				right = right + 1
		while left <= mid:
			temp.append(arr[left])
			left = left + 1
		while right <= high:
			temp.append(arr[right])
			right = right + 1
		i = low
		while i <= high:
			arr[i] = temp[i - low]
			i = i + 1


class Solution:

	def sortArr(self, arr, n):
		arr.sort()
		return arr
		arr = [5, 2, 4, 1]
		b = Solution()
		c = b.sortArr(arr, n)


def quicksort(arr):
	if len(arr) <= 1:
		return arr
	else:
		pivot = arr[0]
		less = [x for x in arr[1:] if x <= pivot]
		greater = [x for x in arr[1:] if x > pivot]
		return quicksort(less) + [pivot] + quicksort(greater)

class Solution:

	def sortArr(self, list, n):
		return quicksort(list)


class Solution:

	def sortArr(self, arr, n):
		arra = sorted(arr)
		return arra


class Solution:

	def sortArr(self, arr, n):
		s = sorted(arr)
		return s


class Solution:

	def merge(self, a, p, mid, q):
		b = [0] * (q - p + 1)
		k = 0
		(u, v) = (p, mid + 1)
		while u <= mid and v <= q:
			if a[u] < a[v]:
				b[k] = a[u]
				u += 1
			else:
				b[k] = a[v]
				v += 1
			k += 1
		while u <= mid:
			b[k] = a[u]
			u += 1
			k += 1
		while v <= q:
			b[k] = a[v]
			v += 1
			k += 1
		for i in range(k):
			a[p + i] = b[i]

	def mergeSort(self, arr, p, q):
		mid = (p + q) // 2
		if mid > p:
			self.mergeSort(arr, p, mid)
		if mid < q:
			self.mergeSort(arr, mid + 1, q)
		if mid > p or mid < q:
			self.merge(arr, p, mid, q)

	def sortArr(self, arr, n):
		self.mergeSort(arr, 0, n - 1)
		return arr


class Solution:

	def sortArr(self, arr, n):
		ans = sorted(arr)
		return ans


class Solution:

	def sortArr(self, arr, n):

		def partition(arr, low, high):
			swap_index = low - 1
			pivot = arr[high]
			for i in range(low, high):
				if arr[i] <= pivot:
					swap_index += 1
					(arr[swap_index], arr[i]) = (arr[i], arr[swap_index])
			(arr[swap_index + 1], arr[high]) = (arr[high], arr[swap_index + 1])
			return swap_index + 1

		def quick_sort(arr, low, high):
			if low < high:
				pi = partition(arr, low, high)
				quick_sort(arr, low, pi - 1)
				quick_sort(arr, pi + 1, high)
		quick_sort(arr, 0, n - 1)
		return arr


import heapq

class Solution:

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