Given an array Arr[], write a program that segregates even and odd numbers. The program should put all even numbers first in sorted order, and then odd numbers in sorted order.
Note :- You don't have to return the array, you just have to modify it in-place.
Example 1:
Input: 
N = 7
Arr[] = {12, 34, 45, 9, 8, 90, 3}
Output: 8 12 34 90 3 9 45
Explanation: Even numbers are 12, 34,
8 and 90. Rest are odd numbers. After
sorting even numbers 8 12 34 90 and 
after sorting odd numbers 3 9 45. Then
concat both.
Example 2:
Input: 
N = 5
Arr[] = {0, 1, 2, 3, 4}
Output: 0 2 4 1 3
Explanation: 0 2 4 are even and 1 3
are odd numbers.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function segregateEvenOdd() which takes the array of integers arr[] and n as parameters and returns void. You need to modify the array itself.
Expected Time Complexity: O(N log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ Arr[i] <=10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N log(N))
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:



	def segregateEvenOdd(self,arr, n):

		# code here

Solutions:
class Solution:

	def segregateEvenOdd(self, arr, n):
		e = []
		odd = []
		for i in range(n):
			if arr[i] % 2 == 0:
				e.append(arr[i])
			else:
				odd.append(arr[i])
		e.sort()
		odd.sort()
		l3 = []
		l3 = e + odd
		for i in range(n):
			arr[i] = l3[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		left = 0
		right = n - 1
		while left < right:
			while arr[left] % 2 == 0 and left < right:
				left += 1
			while arr[right] % 2 == 1 and left < right:
				right -= 1
			if left < right:
				(arr[left], arr[right]) = (arr[right], arr[left])
				left += 1
				right -= 1
		even = [num for num in arr if num % 2 == 0]
		odd = [num for num in arr if num % 2 == 1]
		even.sort()
		odd.sort()
		arr[:] = even + odd


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		even.sort()
		odd.sort()
		even.extend(odd)
		arr[:] = even
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		(l1, l2) = ([], [])
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
			else:
				l2.append(i)
		l1.sort()
		l2.sort()
		l1.extend(l2)
		arr[:] = l1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		(m1, m2) = ([], [])
		for i in arr:
			if i % 2 == 0:
				m1.append(i)
			else:
				m2.append(i)
		m1.sort()
		m2.sort()
		m1.extend(m2)
		arr[:] = m1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		arr.sort()
		b = []
		c = []
		for i in range(0, len(arr)):
			if arr[i] % 2 == 0:
				b.append(arr[i])
			else:
				c.append(arr[i])
		arr[:] = b + c
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		even_arr = []
		odd_arr = []
		for i in arr:
			if i % 2 == 0:
				even_arr.append(i)
		even_arr.sort()
		for i in arr:
			if i % 2 != 0:
				odd_arr.append(i)
		odd_arr.sort()
		arr.clear()
		arr.extend(even_arr)
		arr.extend(odd_arr)


class Solution:

	def segregateEvenOdd(self, arr, n):
		arr.sort()
		even = []
		odd = []
		for i in range(n):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			if arr[i] % 2 == 1:
				odd.append(arr[i])
		a = even + odd
		for i in range(n):
			arr[i] = a[i]
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		odd.sort()
		even.sort()
		even = even + odd
		for i in range(len(arr)):
			arr[i] = even[i]


class Solution:

	def segregateEvenOdd(self, a, n):
		even = []
		odd = []
		for i in a:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		a.clear()
		even.sort()
		odd.sort()
		a.extend(even + odd)


class Solution:

	def segregateEvenOdd(self, arr, n):
		li1 = []
		li2 = []
		for i in range(n):
			if arr[i] % 2 == 0:
				li1.append(arr[i])
			else:
				li2.append(arr[i])
		li1.sort()
		li2.sort()
		li1.extend(li2)
		arr[:] = li1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		i = []
		j = []
		for num in arr:
			if num % 2 == 0:
				i.append(num)
			else:
				j.append(num)
		i.sort()
		j.sort()
		arr.clear()
		arr.extend(i)
		arr.extend(j)


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for I in arr:
			if I % 2 == 0 or I == 0:
				even.append(I)
			else:
				odd.append(I)
		a = sorted(even)
		b = sorted(odd)
		c = a + b
		arr[:] = c
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for num in arr:
			if num % 2 == 0:
				even.append(num)
			else:
				odd.append(num)
		even.sort()
		odd.sort()
		arr.clear()
		arr.extend(even)
		arr.extend(odd)


class Solution:

	def segregateEvenOdd(self, arr, n):
		a = []
		b = []
		arr.sort()
		for i in arr:
			if i % 2 == 0:
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		a.extend(b)
		arr[:] = a
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		res1 = []
		res2 = []
		res = []
		for i in arr:
			if i % 2 == 0:
				res1.append(i)
			else:
				res2.append(i)
		res1.sort()
		res2.sort()
		res1.extend(res2)
		arr[:] = res1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		arr.sort()
		ans = [None] * n
		cnt = 0
		for i in range(n):
			if arr[i] % 2 == 0:
				ans[cnt] = arr[i]
				cnt += 1
		for i in range(n):
			if arr[i] % 2 != 0:
				ans[cnt] = arr[i]
				cnt += 1
		for i in range(n):
			arr[i] = ans[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		(L1, L2) = ([], [])
		for i in arr:
			if i % 2 == 0:
				L1.append(i)
			else:
				L2.append(i)
		L1.sort()
		L2.sort()
		L1.extend(L2)
		arr[:] = L1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		l1 = sorted([i for i in arr if i % 2 == 0])
		l2 = sorted([i for i in arr if i % 2 != 0])
		arr[:] = l1 + l2
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		odd_list = []
		even_list = []
		for i in arr:
			if i % 2 == 0:
				even_list.append(i)
			else:
				odd_list.append(i)
		even_list.sort()
		odd_list.sort()
		even_list.extend(odd_list)
		arr[:] = even_list


class Solution:

	def segregateEvenOdd(self, arr, n):
		li1 = []
		li2 = []
		for i in arr:
			if i % 2 == 0:
				li1.append(i)
			elif i % 2 != 0:
				li2.append(i)
		li1.sort()
		li2.sort()
		s = li1 + li2
		for i in range(n):
			arr[i] = s[i]
		return arr[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for i in range(n):
			if arr[i] % 2 == 0:
				even.append(arr[i])
				continue
			else:
				odd.append(arr[i])
				continue
		even.sort()
		odd.sort()
		arr.clear()
		for j in range(len(even)):
			arr.append(even[j])
		for k in range(len(odd)):
			arr.append(odd[k])


class Solution:

	def segregateEvenOdd(self, arr, n):
		(l, r) = (0, n - 1)
		while l <= r:
			while l < n and arr[l] % 2 == 0:
				l += 1
			while r >= 0 and arr[r] % 2 != 0:
				r -= 1
			if l < r:
				(arr[l], arr[r]) = (arr[r], arr[l])
		i = 0
		for x in sorted(arr[:r + 1]):
			arr[i] = x
			i += 1
		for x in sorted(arr[l:]):
			arr[i] = x
			i += 1


class Solution:

	def segregateEvenOdd(self, arr, n):
		o = []
		e = []
		for i in range(n):
			if arr[i] % 2 == 0:
				e.append(arr[i])
			else:
				o.append(arr[i])
		o.sort()
		e.sort()
		e.extend(o)
		arr[:] = e[:]


class Solution:

	def segregateEvenOdd(self, arr, n):
		arr.sort()
		liOdd = []
		liEven = []
		for i in range(n):
			if arr[i] % 2 == 0:
				liEven.append(arr[i])
			else:
				liOdd.append(arr[i])
		arr[:] = liEven + liOdd
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		j = 0
		for i in range(n):
			if arr[i] % 2 == 0:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 1
		arr[:j] = sorted(arr[:j])
		arr[j:] = sorted(arr[j:])


class Solution:

	def segregateEvenOdd(self, arr, n):
		list1 = [i for i in arr if i % 2 == 0]
		list2 = [i for i in arr if i % 2 != 0]
		list3 = sorted(list1) + sorted(list2)
		for i in range(len(arr)):
			arr[i] = list3[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		arr.sort()
		ev = []
		od = []
		for i in range(n):
			if arr[i] % 2 == 0:
				ev.append(arr[i])
			else:
				od.append(arr[i])
		a = ev + od
		for i in range(n):
			arr[i] = a[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		(p, q) = (0, 0)
		for n in arr:
			if n % 2 == 0:
				even.append(n)
				p += 1
			else:
				odd.append(n)
				q += 1
		even.sort()
		odd.sort()
		(i, j) = (0, 0)
		r = 0
		while i < p:
			arr[r] = even[i]
			r += 1
			i += 1
		while j < q:
			arr[r] = odd[j]
			j += 1
			r += 1


class Solution:

	def segregateEvenOdd(self, arr, n):
		li1 = []
		li2 = []
		for i in range(n):
			if arr[i] % 2 == 0:
				li1.append(arr[i])
		li1.sort()
		for i in range(n):
			if arr[i] % 2 != 0:
				li2.append(arr[i])
		li2.sort()
		for i in range(len(li1)):
			arr[i] = li1[i]
		for i in range(len(li2)):
			arr[i + len(li1)] = li2[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		a = sorted((i for i in arr if i % 2 == 0))
		b = sorted((i for i in arr if i % 2 != 0))
		arr[:] = a + b
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = 0
		odd = n - 1
		while even < odd:
			if arr[even] % 2 == 0:
				even += 1
			else:
				(arr[even], arr[odd]) = (arr[odd], arr[even])
				odd -= 1
		arr.sort(key=lambda x: [x % 2, x])
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		a = [x for x in arr if x % 2 == 0]
		a.sort()
		b = [x for x in arr if x % 2 != 0]
		b.sort()
		arr[:] = a[:] + b[:]
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		x = []
		j = 0
		y = []
		for i in range(n):
			if arr[i] % 2 == 0:
				x.append(arr[i])
				j += 1
			if arr[i] % 2 == 1:
				y.append(arr[i])
		even = sorted(x)
		odd = sorted(y)
		arr[j:] = odd
		arr[:j] = even


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		arr1 = sorted(even) + sorted(odd)
		for i in range(n):
			arr[i] = arr1[i]
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		l = []
		ll = []
		for i in arr:
			if i % 2 == 0:
				l.append(i)
			else:
				ll.append(i)
		l.sort()
		ll.sort()
		arr[:] = (l + ll)[:]


class Solution:

	def segregateEvenOdd(self, arr, n):
		odd = []
		even = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		even.sort()
		odd.sort()
		arr = even + odd
		for x in arr:
			print(x, end=' ')
		print()


class Solution:

	def segregateEvenOdd(self, arr, n):
		odd_arr = []
		even_arr = []
		for i in range(n):
			if arr[i] % 2:
				odd_arr.append(arr[i])
			else:
				even_arr.append(arr[i])
		odd_arr.sort()
		even_arr.sort()
		arr[:] = even_arr + odd_arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		even = sorted(even)
		odd = sorted(odd)
		arr.clear()
		arr.extend(even)
		arr.extend(odd)


class Solution:

	def segregateEvenOdd(self, arr, n):
		even = []
		odd = []
		for (i, each) in enumerate(arr):
			if each % 2 == 0:
				even.append(each)
			else:
				odd.append(each)
		even = sorted(even)
		odd = sorted(odd)
		for (i, each) in enumerate(even):
			arr[i] = even[i]
		idx = len(even)
		for (i, each) in enumerate(odd):
			arr[idx] = odd[i]
			idx += 1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		l = []
		t = []
		arr.sort()
		for i in range(n):
			if arr[i] % 2 == 0:
				l.append(arr[i])
			else:
				t.append(arr[i])
		w = l + t
		arr[:] = w[:]
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		l = []
		arr.sort()
		for i in arr:
			if i % 2 == 0:
				l.append(i)
		for i in arr:
			if i % 2 != 0:
				l.append(i)
		for i in range(len(l)):
			arr[i] = l[i]
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		arr.sort()
		i = 0
		for j in arr:
			if arr[i] % 2 == 1:
				arr.append(arr.pop(i))
			else:
				i += 1
		return arr


class Solution:

	def segregateEvenOdd(self, arr, n):
		(o, e) = ([], [])
		for elem in arr:
			e.append(elem) if elem % 2 == 0 else o.append(elem)
		e.sort()
		o.sort()
		arr[:] = e + o


class Solution:

	def segregateEvenOdd(self, arr, n):
		e = []
		o = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			elif i % 2 != 0:
				o.append(i)
		x = sorted(e)
		y = sorted(o)
		z = x + y
		for i in range(n):
			arr[i] = z[i]
		return z[i]


class Solution:

	def segregateEvenOdd(self, arr, n):
		x = []
		y = []
		for i in arr:
			if i % 2 == 0:
				x.append(i)
			else:
				y.append(i)
		x.sort()
		y.sort()
		arr.clear()
		arr[:] = list(x) + list(y)


class Solution:

	def segregateEvenOdd(self, arr, n):
		e = [i for i in arr if i % 2 == 0]
		o = [i for i in arr if i % 2 != 0]
		s = sorted(e) + sorted(o)
		arr[:] = s[:]
		return arr