ISI2025-MCS-PCB (CS) | Question: 3

Question

Suppose $X=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ is an array of numbers (not necessarily integers) sorted in the ascending order, and $Y=\left(y_{1}, y_{2}, \ldots, y_{n}\right)$ is the array constructed as $y_{i}=f\left(x_{1}\right)$ for $i=1,2, \ldots, n$, where
\[
f(x)=(x+1)(x-1)(x-3)
\]

1. Describe an algorithm that sorts $Y$ using $O(n)$ comparisons.
2. Provide justification for the correctness and the number of comparisons used by your algorithm.