主观题：The expected run length

Suppose that the internal memory can handle $$M$$ = 7 records at a time.  Given the input sequence { 19, 12, 25, 31, 56, 21, 40, 16, 29, 14, 35, 23 }.  What are the runs generated by the replacement selection?

What is the best case?  How about the worst case?

Why  is the expected length of a run generated by replacement selection $$2M$$ (where $$M$$ is the internal memory size)?






答案：