Problem $5$: Create $[20$ points$]$

You work for a company that receives timestamped orders from several stations. Because different

stations are located at different distances, not all orders are received in the order in which they

were placed at the stations. For example, you might receive an order with an earlier timestamp

after one, or several, later orders have already been received. In this problem we will focus only on

the timestamps of the orders.

To simplify this problem, assume that each timestamp is an integer, all timestamps are differ$-$

ent, and for any two timestamps, the earlier timestamp corresponds to a smaller integer than the

later timestamp. The timestamps in the stream are not in their correct order, but you have some

failsafe procedure that ensures that every timestamp $($integer$)$ in the stream is at most $50$ posi$-$

tions away from its correctly sorted position. You want to fulfill the order in the orders in which

they were places. Your job is to output a stream of correctly sorted timestamps.

Design an algorithm that outputs the timestamps in the correct order. You can only use a con$-$

stant amount of storage, i$.$e$.,$ the memory used should be independent of the total number of

timestamps processed $($otherwise an increased volume of orders would be unsustainable$).$ Make

sure to do the following $3$ things: $1)$ Describe your algorithm, $2)$ Give an argument regarding the

correctness of your algorithm $($i$.$e$.,$ why does your algorithm give a correctly sorted stream$),$ and

$3)$ State and briefly justify the time complexity of your algorithm considering n as total number of

timestamps, and every timestamp is at most k $($in this case k $=50,$ but give your solution in terms

of k$)$ positions away from its correctly sorted position. Be sure to double check that you have

done all three things.Problem $5$: Create $[20$ points$]$

You work for a company that receives timestamped orders from several stations. Because different

stations are located at different distances, not all orders are received in the order in which they

were placed at the stations. For example, you might receive an order with an earlier timestamp

after one, or several, later orders have already been received. In this problem we will focus only on

the timestamps of the orders.

To simplify this problem, assume that each timestamp is an integer, all timestamps are differ$-$

ent, and for any two timestamps, the earlier timestamp corresponds to a smaller integer than the

later timestamp. The timestamps in the stream are not in their correct order, but you have some

failsafe procedure that ensures that every timestamp $($integer$)$ in the stream is at most $50$ posi$-$

tions away from its correctly sorted position. You want to fulfill the order in the orders in which

they were places. Your job is to output a stream of correctly sorted timestamps.

Design an algorithm that outputs the timestamps in the correct order. You can only use a con$-$

stant amount of storage, i$.$e$.,$ the memory used should be independent of the total number of

timestamps processed $($otherwise an increased volume of orders would be unsustainable$).$ Make

sure to do the following $3$ things: $1)$ Describe your algorithm, $2)$ Give an argument regarding the

correctness of your algorithm $($i$.$e$.,$ why does your algorithm give a correctly sorted stream$),$ and

State and briefly justify the time complexity of your algorithm considering $n$ as total number of

timestamps, and every timestamp is at most $k($in this case $k=50,$ but give your solution in terms

of $k)$ positions away from its correctly sorted position. Be sure to double check that you have

done all three things.