$6.$For different tasks, we often need to search for things. And most of the time, we sort the dataset before performing search operations. Suppose, you are given the following list of numbers:

$[2,5,1\mathrm{.}2,6\mathrm{.}7,1\mathrm{.}7,9\mathrm{.}3,2\mathrm{.}2,7\mathrm{.}7,0,4,5\mathrm{.}1,2,5,5\mathrm{.}2]$

To search an element in an unsorted array, we need O$($N$)$ time using linear search. Binary search works in O$($logN$)$ time but the array needs to be sorted beforehand which takes at least O$($NlogN$)$ time in general. Why would you then sort the array first and then perform binary search instead of just performing linear search? $[2]$

Can you modify count sort so that it may work with negative integers as well? $[2]$

Can you modify count sort so that it may work with the given list? $[2]$

$7.$ You are given a list of n integers where the even indices hold numbers in decreasing order and the odd indices hold numbers in increasing order. For example, this is a list of n$=8$ integers.

Index

$0$

$1$

$2$

$3$

$4$

$5$

$6$

$7$

Number

$23$

$2$

$19$

$3$

$7$

$11$

$5$

$13$

$[$Explanation: The indices $1,3,5,$ and $7$ have numbers $2,3,11,$ and $13$ in increasing order. The indices $0,2,4,$ and $6$ have numbers $23,19,7$ and $5$ in decreasing order.$]$

Propose a linear time algorithm to sort the list. $[1]$

Present your algorithm with pseudocode$/$programmable code$/$step$-$by$-$step logical instructions. $[3]$