You are given a sequence $x_1,x_2,$dots,$x_n$ of $n$ real numbers between $0$ and $1($inclusive$).$ You want

to reorder the numbers such that the sum of the difference between each pair of adjacent elements

is less than $2.$ That is$,$ you want to find a permutation $y_1,y_2,$dots,$y_n$ where

For example, if we have the sequence $0\mathrm{.}9,0\mathrm{.}2,0\mathrm{.}8,0\mathrm{.}1,0\mathrm{.}3,$ the sum of differences is

$|0\mathrm{.}9-0\mathrm{.}2|+|0\mathrm{.}2-0\mathrm{.}8|+|0\mathrm{.}8-0\mathrm{.}1|+|0\mathrm{.}1-0\mathrm{.}3|=0\mathrm{.}6+0\mathrm{.}6+0\mathrm{.}7+0\mathrm{.}3=2\mathrm{.}2>2.$

If we rearrange the numbers as $0\mathrm{.}2,0\mathrm{.}9,0\mathrm{.}8,0\mathrm{.}1,0\mathrm{.}3,$ the sum is then

Design an algorithm that finds such an order in $O(n)$ time.

Hint: Split the interval $0,1$ into $n$ smaller ranges. The BuCKet$-$SorT algorithm might provide

inspiration. $($Note however that BUCKET$-$SoRT is not a sorting algorithm!$)$

Rubric.

In English, describe an algorithm that rearranges the sequence such that the given sum is

less than $2.$

Prove that the sequence created by your algorithm satisfies the difference requirement.

Justify that your algorithm runs in $O(n)$ time.

Expected response length: up to one page.

Please do this question i$\text{'}$m so stuck