Given an array arr[] of N distinct integers, output the array in such a way that the first element is first maximum and the second element is the first minimum, and so on.
 
Example 1:
Input: N = 7, arr[] = {7, 1, 2, 3, 4, 
                                5, 6}
Output: 7 1 6 2 5 3 4
Explanation:The first element is first 
maximum and second element is first 
minimum and so on.
Example 2:
Input: N = 8, arr[] = {1, 6, 9, 4, 3, 
                             7, 8, 2}
Output: 9 1 8 2 7 3 6 4
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function alternateSort() that takes array arr and integer N as parameters and returns the desired array as output.
 
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{6}

Difficulty: EASY
Tags: Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(NlogN).
Expected Auxiliary Space: O(N).

Starter code:
class Solution:

    def alternateSort(self,arr, N):

        # Your code goes here

Solutions:
class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		l = []
		h = []
		for i in range(len(arr) // 2):
			l.append(arr[i])
		for i in range(len(arr) // 2, len(arr)):
			h.append(arr[i])
		h = h[::-1]
		res = []
		for i in range(min(len(l), len(h))):
			res.append(h[i])
			res.append(l[i])
		for j in range(len(l), len(h)):
			res.append(h[j])
		for j in range(len(h), len(l)):
			res.append(l[j])
		return res


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		low = 0
		high = N - 1
		arr1 = []
		while low < high:
			arr1.append(arr[high])
			high -= 1
			arr1.append(arr[low])
			low += 1
		if N % 2 == 1:
			arr1.append(arr[low])
		return arr1


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		n = N // 2
		a = arr[:n]
		b = arr[n:]
		b.sort(reverse=True)
		arr[::2] = b[:]
		arr[1::2] = a[:]
		return arr


class Solution:

	def alternateSort(self, arr, N):
		l = []
		arr.sort()
		for i in range(len(arr) // 2):
			l.append(arr[-(i + 1)])
			l.append(arr[i])
		if len(arr) % 2 == 1:
			l.append(arr[N // 2])
		return l


class Solution:

	def alternateSort(self, a, N):
		a.sort()
		ans = []
		if N % 2 == 0:
			for i in range(1, N // 2 + 1):
				ans.append(a[-i])
				ans.append(a[i - 1])
		else:
			for i in range(1, N // 2 + 1):
				ans.append(a[-i])
				ans.append(a[i - 1])
			ans.append(a[N // 2])
		return ans


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		start = 0
		end = N - 1
		dict = [0] * N
		if N % 2 == 0:
			for x in range(0, N - 1, 2):
				(dict[x], dict[x + 1]) = (arr[end], arr[start])
				start += 1
				end -= 1
		else:
			for x in range(0, N - 1, 2):
				(dict[x], dict[x + 1]) = (arr[end], arr[start])
				start += 1
				end -= 1
			dict[-1] = arr[int(N / 2)]
		return dict


class Solution:

	def alternateSort(self, arr, N):
		a.sort()
		for i in range(N // 2):
			a.insert(i * 2, a.pop(-1))
		return a


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		i = 0
		j = len(arr) - 1
		res = []
		while i < j:
			res.append(arr[j])
			res.append(arr[i])
			i = i + 1
			j = j - 1
		if N % 2 != 0:
			mid = (i + j) // 2
			res.append(arr[mid])
		return res
		print(res)


class Solution:

	def alternateSort(self, arr, N):
		res = []
		arr.sort()
		i = 0
		j = N - 1
		if N % 2 == 0:
			while i <= j:
				res.append(arr[j])
				res.append(arr[i])
				i += 1
				j -= 1
		else:
			while i < j:
				res.append(arr[j])
				res.append(arr[i])
				i += 1
				j -= 1
			res.append(arr[N // 2])
		return res


class Solution:

	def alternateSort(self, arr, N):
		ans = []
		arr = sorted(arr)
		i = 0
		j = len(arr) - 1
		while i < j:
			ans.append(arr[j])
			ans.append(arr[i])
			i += 1
			j -= 1
		if len(arr) % 2 != 0:
			ans.append(arr[i])
		return ans


class Solution:

	def alternateSort(self, arr, N):
		t = sorted(arr)
		j = 0
		for i in range(0, N // 2, 1):
			arr[j] = t[-(i + 1)]
			arr[j + 1] = t[i]
			j = j + 2
		if N % 2 != 0:
			arr[j] = t[N // 2]
		return arr


class Solution:

	def alternateSort(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(arr2[i])
				new_arr.append(arr1[i])
		else:
			for i in range(N // 2 + 1):
				new_arr.append(arr2[i])
				new_arr.append(arr1[i])
			new_arr.pop()
		return new_arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		lst = []
		i = 0
		j = N - 1
		while i <= j:
			lst.append(arr[j])
			lst.append(arr[i])
			j -= 1
			i += 1
		if N % 2 != 0:
			lst.pop()
		return lst


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		j = 0
		if N % 2 == 0:
			mid = N // 2
		else:
			mid = N // 2 + 1
		for i in range(N, mid, -1):
			arr.insert(j, arr[-1])
			arr.pop()
			j += 2
		return arr


class Solution:

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


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		l1 = arr[:len(arr) // 2]
		l2 = arr[len(arr) // 2:]
		arr[::2] = l2[::-1]
		arr[1::2] = l1[:]
		return arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		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]
		return ans


class Solution:

	def alternateSort(self, arr, N):
		if len(arr) == 1:
			return arr
		else:
			arr = sorted(arr)
			mini = arr[0:N // 2]
			maxi = arr[N:N // 2 - 1:-1]
			arr.clear()
			lmin = len(mini)
			lmax = len(maxi)
			for i in range(lmin):
				arr.append(maxi[i])
				arr.append(mini[i])
			if lmax > lmin:
				arr.extend(maxi[lmin:lmax])
			return arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		(l, r) = (0, N - 1)
		x = []
		while l <= r:
			if l == r:
				x.append(arr[r])
			else:
				x.append(arr[r])
				x.append(arr[l])
			r = r - 1
			l = l + 1
		return x


class Solution:

	def alternateSort(self, arr, N):
		a = sorted(arr)
		l = [0] * N
		(x, y) = (1, 0)
		for i in range(0, N, 2):
			l[i] = a[-x]
			x += 1
		for i in range(1, N, 2):
			l[i] = a[y]
			y += 1
		return l


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		if N % 2 == 0:
			a1 = arr[:N // 2]
			a2 = [x for x in reversed(arr)]
			a2 = a2[:N // 2]
			arr[0::2] = a2
			arr[1::2] = a1
			return arr
		else:
			a1 = arr[:N // 2]
			a2 = [x for x in reversed(arr)]
			a2 = a2[:N // 2 + 1]
			arr[0::2] = a2
			arr[1::2] = a1
			return arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		x = n // 2
		l = arr[:x]
		r = arr[x:]
		flg = 0
		r.sort(reverse=True)
		j = 0
		k = 0
		for i in range(n):
			if flg == 0:
				arr[i] = r[j]
				flg = 1
				j += 1
			else:
				arr[i] = l[k]
				flg = 0
				k += 1
		return arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort(reverse=True)
		if N < 3:
			return arr
		for i in range(N // 2):
			arr.insert(i * 2 + 1, arr.pop(-1))
		return arr


class Solution:

	def alternateSort(self, arr, N):
		result = []
		arr.sort()
		for index in range(N // 2):
			result.append(arr[-index - 1])
			result.append(arr[index])
		result.append(arr[N // 2]) if N % 2 == 1 else None
		return result


class Solution:

	def alternateSort(self, arr, n):
		arr.sort()
		lt = [0] * n
		x = 1
		y = 0
		for i in range(0, n, 2):
			lt[i] = arr[-x]
			x += 1
		for i in range(1, n, 2):
			lt[i] = arr[y]
			y += 1
		return lt


class Solution:

	def alternateSort(self, arr, N):
		list_return = []
		arr.sort()
		arr_first = arr[:N // 2]
		arr_end = arr[N // 2:]
		arr_end.reverse()
		for i in range(0, N):
			if i % 2 == 0:
				list_return.append(arr_end.pop(0))
			else:
				list_return.append(arr_first.pop(0))
		return list_return


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		output = []
		for i in range(N):
			if i % 2 == 0:
				output.append(arr[-1])
				arr.pop()
			elif i % 2 != 0:
				output.append(arr[0])
				arr.pop(0)
		return output


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		an = []
		for i in range(0, N // 2):
			an.append(arr[N - i - 1])
			an.append(arr[i])
		if N & 1:
			an.append(arr[N // 2])
		return an


class Solution:

	def alternateSort(self, arr, N):
		copy = arr[::-1]
		copy.sort()
		i = 0
		j = N - 1
		k = 0
		while k < N and i <= j:
			if k % 2 == 0:
				arr[k] = copy[j]
				j -= 1
				k += 1
			else:
				arr[k] = copy[i]
				i += 1
				k += 1
		return arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		ans = [0] * N
		left = 0
		right = N - 1
		i = 0
		while right >= left:
			if i % 2 == 0:
				ans[i] = arr[right]
				right -= 1
			else:
				ans[i] = arr[left]
				left += 1
			i += 1
		return ans


class Solution:

	def alternateSort(self, arr, n):
		arr.sort()
		p = []
		p.append(arr[n - 1])
		x = 0
		y = n - 2
		for i in range(1, n):
			if i % 2 != 0:
				p.append(arr[x])
				x += 1
			else:
				p.append(arr[y])
				y -= 1
		return p


class Solution:

	def alternateSort(self, arr, N):
		l = 0
		r = n - 1
		a = sorted(list(arr))
		b = []
		while l <= r:
			if l == r:
				b.append(a[l])
			else:
				b.append(a[r])
				b.append(a[l])
			l += 1
			r -= 1
		return b


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		mini = 0
		maxi = N - 1
		l = []
		M = max(arr) + 1
		for i in range(N):
			if i % 2 == 0:
				arr[i] = arr[i] + arr[maxi] % M * M
				maxi -= 1
			else:
				arr[i] = arr[i] + arr[mini] % M * M
				mini += 1
			l.append(int(arr[i] // M))
		return l


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		arr_new = []
		first = 0
		last = N - 1
		for i in range(0, N):
			if i % 2 == 0:
				arr_new.append(arr[last])
				last -= 1
			else:
				arr_new.append(arr[first])
				first += 1
		return arr_new


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		m = N - 1
		n = 0
		output = []
		while n <= m:
			if n == m:
				output.append(arr[m])
				break
			output.append(arr[m])
			output.append(arr[n])
			m -= 1
			n += 1
		return output


class Solution:

	def alternateSort(self, arr, N):
		des = sorted(arr, reverse=True)
		asc = sorted(arr)
		j = 0
		k = 0
		for i in range(N):
			if i % 2 == 0:
				arr[i] = des[j]
				j += 1
			elif i % 2 != 0:
				arr[i] = asc[k]
				k += 1
		return arr


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		st = 0
		end = n - 1
		l = []
		while st < end:
			l.append(arr[end])
			end -= 1
			l.append(arr[st])
			st += 1
		if N % 2 != 0:
			l.append(arr[st])
		return l


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		(i, j) = (0, N - 1)
		result = [0] * N
		for k in range(N):
			if k % 2 == 0:
				result[k] = arr[j]
				j -= 1
			else:
				result[k] = arr[i]
				i += 1
		return result


class Solution:

	def alternateSort(self, arr, N):
		op = [0] * N
		arr.sort()
		j = 0
		for i in range(1, N, 2):
			op[i] = arr[j]
			j += 1
		j = 0
		arr.sort(reverse=True)
		for i in range(0, N, 2):
			op[i] = arr[j]
			j += 1
		return op


class Solution:

	def alternateSort(self, arr, N):
		if N == 1:
			return arr
		arr = sorted(arr)
		a = []
		if N % 2 == 0:
			for i in range(N // 2):
				a.append(arr[N - i - 1])
				a.append(arr[i])
		else:
			for i in range(N // 2):
				a.append(arr[N - i - 1])
				a.append(arr[i])
			a.append(arr[i + 1])
		return a


class Solution:

	def alternateSort(self, arr, N):
		lst = []
		max = N - 1
		min = 0
		sortarr = sorted(arr)
		for i in range(N):
			if i % 2 == 0:
				lst.append(sortarr[max])
				max -= 1
			else:
				lst.append(sortarr[min])
				min += 1
		return lst


class Solution:

	def alternateSort(self, x, N):
		a = sorted(x)
		b = sorted(x, reverse=True)
		y = []
		if len(x) % 2 == 0:
			for i in range(len(x) // 2):
				y.append(b[i])
				y.append(a[i])
		else:
			for i in range(len(x) // 2 + 1):
				y.append(b[i])
				y.append(a[i])
			y.pop()
		return y


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		array = []
		a = 0
		b = 1
		y = round(N // 2) - 1
		for j in range(0, N // 2, 1):
			array.insert(b, arr[j])
			b = b + 2
		for i in range(N - 1, y, -1):
			array.insert(a, arr[i])
			a = a + 2
		return array


class Solution:

	def alternateSort(self, arr, N):
		a = sorted(arr)
		b = a[::-1]
		l = []
		if N % 2 == 0:
			for i in range(N // 2):
				l.append(b[i])
				l.append(a[i])
		else:
			for i in range(n // 2 + 1):
				l.append(b[i])
				l.append(a[i])
			l.pop()
		return l


def mergesort(arr):
	if len(arr) <= 1:
		return arr
	mid = len(arr) // 2
	left = arr[:mid]
	right = arr[mid:]
	mergesort(left)
	mergesort(right)
	return merge(left, right, arr)

def merge(left, right, arr):
	i = j = k = 0
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			arr[k] = left[i]
			i += 1
		else:
			arr[k] = right[j]
			j += 1
		k += 1
	while i < len(left):
		arr[k] = left[i]
		i += 1
		k += 1
	while j < len(right):
		arr[k] = right[j]
		j += 1
		k += 1
	return arr

class Solution:

	def alternateSort(self, arr, N):
		sortedarr = mergesort(arr)
		ret = []
		for i in range(len(arr) // 2):
			ret.append(arr[len(arr) - 1 - i])
			ret.append(arr[i])
		if len(arr) % 2 == 1:
			ret.append(arr[len(arr) // 2])
		return ret


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		k = 1
		ans = []
		for x in range(N):
			if k:
				ans.append(arr.pop())
			else:
				ans.append(arr[0])
				del arr[0]
			k ^= 1
		return ans


class Solution:

	def alternateSort(self, arr, N):
		l = []
		arr.sort()
		f = True
		low = 0
		high = N - 1
		for i in range(N):
			if f == True:
				k = arr[high]
				high = high - 1
			else:
				k = arr[low]
				low = low + 1
			f = bool(1 - f)
			l.append(k)
		return l


class Solution:

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


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		ans = []
		l = 0
		r = N - 1
		while l < r:
			ans.append(arr[r])
			ans.append(arr[l])
			l += 1
			r -= 1
		if N % 2 == 1:
			l = N // 2
			ans.append(arr[l])
		return ans


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		ans = []
		if N % 2 == 0:
			r = int(N / 2)
			ar1 = arr[:r]
			ar2 = arr[r:]
			ar2.sort(reverse=True)
			for i in range(len(ar1)):
				ans.append(ar2[i])
				ans.append(ar1[i])
			return ans
		else:
			r = N // 2
			ar1 = arr[:r]
			ar2 = arr[r:]
			ar2.sort(reverse=True)
			for i in range(len(ar1)):
				ans.append(ar2[i])
				ans.append(ar1[i])
			ans.append(ar2[-1])
			return ans


class Solution:

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


class Solution:

	def alternateSort(self, arr, N):
		(x, x1, x2) = ([], [], [])
		ao = sorted(arr)
		k = ao[len(ao) // 2]
		do = sorted(arr, reverse=True)
		for i in range(len(ao) // 2):
			x.append(ao[i])
		for i in range(len(do) // 2 + 1):
			x1.append(do[i])
		if len(arr) % 2 == 0:
			for i in range(len(arr) // 2):
				x2.append(x1[i])
				x2.append(x[i])
		else:
			for i in range(len(arr) // 2):
				x2.append(x1[i])
				x2.append(x[i])
			x2.append(k)
		return x2


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		l1 = []
		j = 1
		if N % 2 == 0:
			for i in range(N // 2):
				l1.append(arr[-j])
				l1.append(arr[i])
				j = j + 1
			return l1
		else:
			for i in range(N // 2 + 1):
				l1.append(arr[-j])
				l1.append(arr[i])
				j = j + 1
			l1.pop()
		return l1


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		lst = []
		first = 0
		last = N - 1
		while first < last:
			lst.append(arr[last])
			lst.append(arr[first])
			last = last - 1
			first = first + 1
		if N % 2 != 0:
			lst.append(arr[first])
		return lst


class Solution:

	def alternateSort(self, arr, n):
		arr.sort(reverse=True)
		res = [None] * n
		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
		return res
		print(res)


class Solution:

	def alternateSort(self, arr, N):
		b = []
		arr.sort(reverse=1)
		n = N - 1
		for i in range(int(len(arr) / 2)):
			b.append(arr[i])
			b.append(arr[n - i])
		if N % 2 == 1:
			b.append(arr[int(N / 2)])
		return b


class Solution:

	def alternateSort(self, arr, N):
		arr.sort()
		l = 0
		r = N - 1
		a = []
		f = 0
		for j in range(N):
			if f == 0:
				a.append(arr[r])
				r -= 1
				f = 1
			else:
				a.append(arr[l])
				l += 1
				f = 0
		return a


class Solution:

	def alternateSort(self, arr, N):
		arr1 = sorted(arr)
		arr2 = []
		i = len(arr1) - 1
		arr2 = arr1[len(arr1):0:-1]
		arr2.append(arr1[0])
		j = len(arr2) // 2
		k = 0
		arr3 = []
		while k != j:
			arr3.append(arr2[k])
			arr3.append(arr1[k])
			k += 1
		if len(arr1) % 2 != 0:
			arr3.append(arr2[k])
		return arr3