Consider a situation where your data is almost sorted—for example you are receiving time-stamped stock quotes and earlier quotes may arrive after later quotes because of differences in server loads and network traffic routes. Focus only on the time-stamps. To simplify this problem, assume that each time-stamp is an integer, all time-stamps are different, and for any two time-stamps, the earlier time-stamp corresponds to a smaller integer than the later time-stamp. The time-stamps arrive in a stream that is too large to be kept in memory completely. The time-stamps in the stream are not in their correct order, but you know that every time-stamp (integer) in the stream is at most hundred positions away from its correctly sorted position. Design an algorithm that outputs the time-stamps in the correct order. You can only a constant amount of storage , i.e., the memory used should be independent of the number of time-stamps processed. As a second requirement: your algorithm should use a linked list and NOT a heap.

Answer rating: 100% (QA)

ANSWER The algorithm is as follows We have a set of numbers arranged i... View the full answer