Given an array arr of n integers, task is to print the array in the order – smallest number, largest number, 2nd smallest number, 2nd largest number, 3rd smallest number, 3rd largest number and so on.
Example 1:
Input:
n = 9
arr[] = {1, 9, 2, 8, 3, 7, 4, 6, 5}
Output:
1 9 2 8 3 7 4 6 5
Explanation:
Smallest number is 1. Largest number is 9. 
2nd smallest number is 2. Then 2nd largest
number is 8. And so on.
Example 2:
Input:
n = 4
arr[] = {1, 2, 3, 4}
Output:
1 4 2 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function rearrangeArray() which takes the array of integers arr and n as parameters and returns void. You need to change the array itself.
Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(n)
Constraints: 
1 <= n <= 10^{5}
1 <= arr[i] <=10^{6}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(n*logn)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3



class Solution:
    def rearrangeArray(self, arr, n):
        # code here

Solutions:
class Solution:

	def rearrangeArray(self, arr, n):
		result = []
		arr.sort()
		left = 0
		right = n - 1
		while left < right:
			result.append(arr[left])
			result.append(arr[right])
			left += 1
			right -= 1
		if n % 2 == 1:
			result.append(arr[left])
		for i in range(0, n):
			arr[i] = result[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		if n % 2 != 0:
			N = n // 2 + 1
		else:
			N = n // 2
		a = arr[:N]
		b = arr[N:]
		arr[::2] = a[:]
		arr[1::2] = b[:][::-1]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		left = arr[:n // 2]
		right = arr[n // 2:][::-1]
		l = []
		for i in range(n // 2):
			l.append(left[0])
			left.pop(0)
			l.append(right[0])
			right.pop(0)
		l = l + left + right
		for i in range(n):
			arr[i] = l[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		l = []
		while i < j:
			l.append(arr[i])
			l.append(arr[j])
			i += 1
			j -= 1
		if n % 2 == 1:
			l.append(arr[i])
		for i in range(0, n):
			arr[i] = l[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr1 = sorted(arr)
		arr2 = sorted(arr, reverse=True)
		new_arr = []
		if n % 2 == 0:
			for i in range(n // 2):
				new_arr.append(arr1[i])
				new_arr.append(arr2[i])
		else:
			for i in range(n // 2 + 1):
				new_arr.append(arr1[i])
				new_arr.append(arr2[i])
			new_arr.pop()
		for i in range(n):
			arr[i] = new_arr[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		li = []
		k = 0
		m = -1
		t = sorted(arr)
		for i in range(n):
			if i % 2 == 0:
				li.append(t[k])
				k = k + 1
			else:
				li.append(t[m])
				m = m - 1
		return li


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		clone = arr.copy()
		left = 0
		right = n - 1
		for i in range(n):
			if i % 2 == 0:
				arr[i] = clone[left]
				left += 1
			else:
				arr[i] = clone[right]
				right -= 1


class Solution:

	def rearrangeArray(self, arr, N):
		arr.sort()
		arr = arr[::-1]
		ans = [0] * N
		k = 0
		for i in range(0, N // 2):
			ans[k] = arr[N - 1 - i]
			k += 1
			ans[k] = arr[i]
			k += 1
		if N % 2 != 0:
			ans[N - 1] = arr[N // 2]
		for x in ans:
			print(x, end=' ')


class Solution:

	def rearrangeArray(self, arr, n):
		n = len(arr)
		arr.sort()
		output = [None] * n
		left = 0
		right = n - 1
		for i in range(n):
			if i % 2 == 0:
				output[i] = arr[left]
				left += 1
			else:
				output[i] = arr[right]
				right -= 1
		for i in range(n):
			arr[i] = output[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		p = []
		for index in range(n // 2):
			p.append(arr[index])
			p.append(arr[-index - 1])
		p.append(arr[n // 2]) if n % 2 == 1 else None
		arr[:] = p


class Solution:

	def rearrangeArray(self, arr, n):
		res = [0] * n
		arr.sort()
		l = 0
		r = n - 1
		for i in range(n):
			if i % 2 == 0:
				res[i] = arr[l]
				l += 1
			else:
				res[i] = arr[r]
				r -= 1
		for i in range(n):
			arr[i] = res[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		if n % 2 == 0:
			arr_first = arr[:n // 2]
			arr_end = arr[n // 2:]
			arr_end.reverse()
		else:
			arr_first = arr[:n // 2 + 1]
			arr_end = arr[n // 2:]
			arr_end.reverse()
		if n % 2 == 0:
			for i in range(0, n, 2):
				arr[i] = arr_first.pop(0)
				arr[i + 1] = arr_end.pop(0)
		else:
			for i in range(0, n - 1, 2):
				arr[i] = arr_first.pop(0)
				arr[i + 1] = arr_end.pop(0)
			arr[n - 1] = arr_first.pop(0)


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		value = arr.copy()
		arr.clear()
		for i in range(n):
			if i % 2 == 0:
				arr.append(value[0])
				value.pop(0)
			if i % 2 != 0:
				arr.append(value[-1])
				value.pop(-1)
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		ans = []
		arr.sort()
		for i in arr:
			ans.append(i)
		arr.clear()
		if len(ans) == 1:
			for i in ans:
				arr.append(i)
		elif n % 2 != 0:
			s = ans[:n // 2 + 1]
			b = ans[-1:n // 2:-1]
			c = 0
			for i in range(n // 2):
				arr.append(s[i])
				arr.append(b[i])
				c = i
			c = c + 1
			arr.append(s[c])
		else:
			s = ans[:n // 2]
			b = ans[-1:n // 2 - 1:-1]
			c = 0
			for i in range(n // 2):
				arr.append(s[i])
				arr.append(b[i])


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		t = n // 2
		if n % 2 != 0:
			t = t + 1
		l = arr[:t]
		f = arr[t:]
		f.sort(reverse=True)
		if n % 2 != 0:
			k = 0
			for i in range(0, t - 1):
				arr[k] = l[i]
				arr[k + 1] = f[i]
				k = k + 2
			arr[-1] = l[-1]
		else:
			k = 0
			for i in range(0, t):
				arr[k] = l[i]
				arr[k + 1] = f[i]
				k = k + 2


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		a = arr.copy()
		small = []
		large = []
		m = 0
		if n % 2 == 0:
			m = (0 + len(arr) - 1) // 2 + 1
		else:
			m = (0 + len(arr) - 1) // 2
		for i in range(m):
			temp = a.pop(0)
			small.append(temp)
		for i in a:
			large.append(i)
		large = large[::-1]
		ans = []
		for i in range(n):
			if len(small) == 0 or len(large) == 0:
				break
			if small and large:
				if i % 2 == 0:
					temp = small.pop(0)
					ans.append(temp)
				else:
					temp = large.pop(0)
					ans.append(temp)
		while small:
			temp = small.pop(0)
			ans.append(temp)
		while large:
			temp = large.pop(0)
			ans.append(temp)
		for i in range(n):
			arr[i] = ans[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		tmp = [n]
		arr.sort()
		tmp = arr[:]
		i = 0
		j = n - 1
		for k in range(n):
			if k % 2 == 0:
				arr[k] = tmp[i]
				i += 1
			else:
				arr[k] = tmp[j]
				j -= 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		ans = []
		lo = 0
		hi = len(arr) - 1
		while lo < hi:
			ans.append(arr[lo])
			lo += 1
			ans.append(arr[hi])
			hi -= 1
		ans.append(arr[lo])
		for i in range(n):
			arr[i] = ans[i]


class Solution:

	def rearrangeArray(self, arr, n):
		asc = sorted(arr)
		desc = sorted(arr, reverse=True)
		j = 0
		k = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = asc[j]
				j += 1
			else:
				arr[i] = desc[k]
				k += 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		b = []
		if n > 1:
			for i in range(0, n // 2, 1):
				b.append(arr[i])
				b.append(arr[n - 1 - i])
			if n % 2 != 0:
				b.append(arr[i + 1])
			arr[:] = b[:]


class Solution:

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

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

	def rearrangeArray(self, arr, n):
		self.quicksort(arr, 0, n - 1)
		new = []
		new.append(arr[0])
		for i in range(1, n // 2 + 1):
			new.append(arr[-i])
			new.append(arr[i])
		for i in range(n):
			arr[i] = new[i]


class Solution:

	def mergesort(self, arr):
		if len(arr) > 1:
			mid = len(arr) // 2
			L = arr[:mid]
			R = arr[mid:]
			self.mergesort(L)
			self.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]
				k += 1
				i += 1
			while j < len(R):
				arr[k] = R[j]
				k += 1
				j += 1

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

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

	def rearrangeArray(self, arr, n):
		arr.sort()
		for i in range(1, n // 2 + 1):
			arr.insert(i * 2 - 1, arr.pop(-1))
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		a = sorted(arr)
		(start, end) = (0, n - 1)
		for i in range(n):
			if i & 1 == 0:
				arr[i] = a[start]
				start += 1
			else:
				arr[i] = a[end]
				end -= 1


class Solution:

	def rearrangeArray(self, arr, n):
		l = []
		arr.sort()
		for i in range(int((n + 1) / 2)):
			l.append(arr[i])
			if len(l) < len(arr):
				l.append(arr[-1 - i])
		for i in range(0, n):
			arr[i] = l[i]


class Solution:

	def rearrangeArray(self, arr, n):
		sotred_arr = sorted(arr)
		l = 0
		r = n - 1
		i = 0
		while l < r:
			arr[i] = sotred_arr[l]
			i += 1
			arr[i] = sotred_arr[r]
			i += 1
			l += 1
			r -= 1
		if l == r:
			arr[i] = sotred_arr[l]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		temp = [0] * (n + 1)
		start = 0
		end = n - 1
		for i in range(len(arr)):
			temp[i] = arr[i]
		for i in range(len(arr)):
			if i % 2 == 0:
				arr[i] = temp[start]
				start += 1
			else:
				arr[i] = temp[end]
				end -= 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		res = [None] * n
		arr.sort()
		ptr = 0
		for i in range(0, n, 2):
			res[i] = arr[ptr]
			ptr += 1
		ptr = -1
		for i in range(1, n, 2):
			res[i] = arr[ptr]
			ptr -= 1
		for i in range(n):
			arr[i] = res[i]


class Solution:

	def rearrangeArray(self, arr, n):
		re = []
		arr.sort()
		l = 0
		r = n - 1
		f = 0
		for i in range(n):
			if f == 0:
				re.append(arr[l])
				l += 1
				f = 1
			else:
				re.append(arr[r])
				f = 0
				r -= 1
		arr[:] = re[:]


class Solution:

	def rearrangeArray(self, arr, n):
		a = sorted(arr)
		b = sorted(arr, reverse=True)
		c = []
		if n % 2 == 0:
			for i in range(n // 2):
				c.append(a[i])
				c.append(b[i])
		else:
			for i in range(n // 2 + 1):
				c.append(a[i])
				c.append(b[i])
			c.pop()
		arr[:] = c


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		i = 0
		j = n - 1
		a = []
		while i <= j:
			if i != j:
				a.append(arr[i])
				a.append(arr[j])
			else:
				a.append(arr[i])
			i += 1
			j -= 1
		arr[:] = a


class Solution:

	def rearrangeArray(self, arr, n):
		sorted_arr = sorted(arr)
		for i in range(n // 2):
			arr.append(sorted_arr.pop(0))
			arr.append(sorted_arr.pop())
		if len(sorted_arr):
			arr.append(sorted_arr.pop())
		del arr[:n]


class Solution:

	def rearrangeArray(self, arr, n):
		res = []
		arr.sort()
		l = 0
		r = n - 1
		while l < r:
			res.append(arr[l])
			res.append(arr[r])
			l += 1
			r -= 1
		if n % 2 == 1:
			res.append(arr[l])
		arr[:] = res[:]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		m = arr[-1] + 1
		(mn, mx) = (0, n - 1)
		for i in range(n):
			if i % 2 == 0:
				arr[i] = arr[i] + arr[mn] % m * m
				mn += 1
			else:
				arr[i] = arr[i] + arr[mx] % m * m
				mx -= 1
		for i in range(n):
			arr[i] = arr[i] // m
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		(i, j) = (0, n - 1)
		rearrange = []
		while i <= j:
			if i < j:
				rearrange.append(arr[i])
				rearrange.append(arr[j])
			else:
				rearrange.append(arr[i])
			i += 1
			j -= 1
		arr[:] = rearrange[:]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		res = []
		for i in range(n // 2):
			res.append(arr[i])
			res.append(arr[n - i - 1])
		if n % 2:
			res.append(arr[n // 2])
		for i in range(n):
			arr[i] = res[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		k = 0
		if n % 2 == 0:
			a = n // 2
		else:
			a = n // 2 + 1
		arr.sort()
		lst1 = arr[:a]
		lst2 = sorted(arr[a:], reverse=True)
		if n % 2 == 0:
			for i in range(0, n, 2):
				arr[i] = lst1[k]
				arr[i + 1] = lst2[k]
				k = k + 1
		else:
			for i in range(0, n - 2, 2):
				arr[i] = lst1[k]
				arr[i + 1] = lst2[k]
				k = k + 1
			arr[-1] = lst1[-1]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		brr = [0] * n
		for i in range(0, n):
			brr[i] = arr[i]
		brr.sort()
		p = 0
		q = n - 1
		for i in range(0, n):
			if i % 2 == 0:
				arr[i] = brr[p]
				p += 1
			else:
				arr[i] = brr[q]
				q -= 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr[:] = list(self.seq(arr, n))

	def seq(self, arr, n):
		arr.sort()
		j = n // 2
		i = 0
		while i != j:
			i += 1
			yield arr[i - 1]
			yield arr[-i]
		else:
			if n % 2 != 0:
				yield arr[i]


from itertools import chain

class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		if n % 2 != 0:
			arr[:] = list(chain(*zip(arr[:n // 2 + 1], arr[-1:-n // 2:-1]), [arr[n // 2]]))
		else:
			arr[:] = list(chain(*zip(arr[:n // 2], arr[-1:n // 2 - 1:-1])))


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		newarr = []
		i = 0
		j = len(arr) - 1
		while i <= j:
			newarr.append(arr[i])
			i += 1
			if i <= j:
				newarr.append(arr[j])
				j -= 1
		arr[:] = newarr
		return newarr


class Solution:

	def rearrangeArray(self, arr, n):
		b = arr.copy()
		b.sort()
		start = 0
		end = n - 1
		for i in range(0, n):
			if i % 2 != 0:
				arr[i] = b[end]
				end -= 1
			else:
				arr[i] = b[start]
				start += 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		tmp = n * [None]
		s = 0
		l = n - 1
		flag = 1
		for i in range(n):
			if flag == 1:
				tmp[i] = arr[s]
				s += 1
			else:
				tmp[i] = arr[l]
				l -= 1
			flag = 1 - flag
		for i in range(n):
			arr[i] = tmp[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		lis = [0 for i in range(n)]
		c = 1
		for i in range(len(lis)):
			lis[i] = arr[i]
		for i in range(len(lis)):
			if c == 1:
				arr[i] = lis.pop(0)
				c = 0
			elif c == 0:
				arr[i] = lis.pop()
				c = 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		low = 0
		high = n - 1
		result = []
		while low < high:
			result.append(arr[low])
			low += 1
			result.append(arr[high])
			high -= 1
		if n % 2 == 1:
			result.append(arr[low])
		arr[:] = result[:]


class Solution:

	def rearrangeArray(self, arr, n):
		x = []
		arr.sort()
		le = 0
		ri = n - 1
		while le < ri:
			x.append(arr[le])
			x.append(arr[ri])
			le += 1
			ri -= 1
		if n % 2 == 1:
			x.append(arr[le])
		for i in range(0, n):
			arr[i] = x[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		k = 0
		for i in range(n // 2):
			x = arr.pop()
			arr.insert(2 * k + 1, x)
			k += 1
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		t1 = []
		t2 = []
		f1 = []
		arr.sort()
		if n % 2 == 0:
			t1 = arr[:n // 2]
			t2 = arr[n // 2:]
		else:
			t1 = arr[:n // 2]
			t2 = arr[n // 2:]
		t2.sort(reverse=True)
		for x in range(0, n // 2):
			f1.append(t1[x])
			f1.append(t2[x])
		if len(t2) > len(t1):
			f1.append(t2[len(t2) - 1])
		for j in range(0, n):
			arr[j] = f1[j]


class Solution:

	def rearrangeArray(self, arr, n):
		if len(arr) % 2 != 0:
			mid = len(arr) // 2 + 1
		else:
			mid = len(arr) // 2
		arr.sort()
		temp = [0] * len(arr)
		k = 0
		for i in range(mid):
			temp[k] = arr[i]
			k += 2
		k = 1
		for i in range(len(arr) - 1, mid - 1, -1):
			temp[k] = arr[i]
			k += 2
		for i in range(len(arr)):
			arr[i] = temp[i]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		l = []
		start = 0
		end = n - 1
		while start <= end:
			l.append(arr[start])
			l.append(arr[end])
			end -= 1
			start += 1
		if n % 2 != 0:
			m = l[0:len(l) - 1]
		else:
			m1 = l
		for i in range(n):
			arr[i] = l[i]


class Solution:

	def rearrangeArray(self, arr, n):
		temp = sorted(arr)
		counter = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = temp[i // 2]
			else:
				counter += 1
				arr[i] = temp[n - counter]


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		result = [None] * n
		for i in range(1, n, 2):
			value = arr.pop()
			result[i] = value
		x = 0
		for j in range(0, len(result), 2):
			result[j] = arr[x]
			x = x + 1
		arr.clear()
		for i in range(len(result)):
			arr.append(result[i])


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		a = []
		for i in range(n // 2 + 1):
			a.append(arr[i])
			a.append(arr[n - i - 1])
		for i in range(n):
			arr[i] = a[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		i = 1
		for _ in range(n // 2):
			arr.insert(i, arr.pop())
			i += 2
		return arr


from itertools import cycle

class Solution:

	def rearrangeArray(self, arr, n):
		t = arr
		arr.sort()
		if n % 2 == 1:
			a = arr[0:int(n / 2) + 1]
		else:
			a = arr[0:int(n / 2)]
		t.sort(reverse=True)
		b = t[0:int(n / 2)]
		iters = [iter(a), iter(b)]
		d = list((iter.__next__() for iter in cycle(iters)))
		for i in range(0, n):
			arr[i] = d[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		temp = [0] * n
		arr.sort()
		k = 0
		j = n - 1
		flag = True
		for i in range(n):
			if flag == True:
				temp[i] = arr[k]
				k = k + 1
			else:
				temp[i] = arr[j]
				j = j - 1
			flag = bool(1 - flag)
		for i in range(n):
			arr[i] = temp[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		temp_arr = [0] * (n + 1)
		i = 0
		j = n - 1
		a = 0
		while i <= n // 2 and j >= n // 2:
			temp_arr[a] = arr[i]
			a += 1
			i += 1
			temp_arr[a] = arr[j]
			a += 1
			j -= 1
		for i in range(n):
			arr[i] = temp_arr[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		k = []
		arr.sort()
		for i in range(n):
			k.append(arr[i])
			k.append(arr[n - 1 - i])
		for i in range(n):
			arr[i] = k[i]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		l = len(arr) // 2
		a = arr[:l]
		b = arr[l:]
		c = []
		b.reverse()
		while a or b:
			if len(a):
				c.append(a.pop(0))
			if len(b):
				c.append(b.pop(0))
		arr[:] = c[:]
		return arr


class Solution:

	def rearrangeArray(self, arr, n):
		arr.sort()
		res = arr.copy()
		j = n - 1
		k = 0
		for i in range(n):
			if i % 2 == 0:
				arr[i] = res[k]
				k += 1
			else:
				arr[i] = res[j]
				j -= 1